RECUR23 Editorial

editorial
1

Problem Explanation

We are given an array A and an integer sum, We have to give all unique combinations of the elements of A, such that the sum of the chosen elements is equal to B.

Approach

We use Recursion to get every combinations from the array. If an element is less than or equal to the remaining sum, we use it in the combination and call the function and pass the remaining sum after subtracting the current element. And we call the function once excluding the current element and moving on to the next element. For every element we can be sure that these are the only two choices for making a combination. We push the combinations in a set to make sure the combinations are unique.

Code

#include <bits/stdc++.h>
using namespace std;
void uniqueCombinationsSum(vector<int> &arr, int sum, int n, set<vector<int>> &allCombinations, vector<int> &currentCombination){
    if(sum==0){
        allCombinations.insert(currentCombination);
    }
    if(sum>=arr[n])
    {
        currentCombination.push_back(arr[n]);
        uniqueCombinationsSum(arr, sum-arr[n], n, allCombinations, currentCombination);
        currentCombination.pop_back();
    }
    if(n+1<arr.size() && sum>=arr[n+1]){
        uniqueCombinationsSum(arr, sum, n+1, allCombinations, currentCombination);
    }
}
int main() {
    int t;
    cin>>t;
    while(t--){
        int n, sum;
        cin>>n>>sum;
        vector<int> arr;
        for(int i=0; i<n; i++){
            int temp;
            cin>>temp;
            arr.push_back(temp);
        }
        vector<int> currentCombination;
        set<vector<int>> allCombinations;
        sort(arr.begin(), arr.end());
        uniqueCombinationsSum(arr, sum, 0, allCombinations, currentCombination);
        cout<<allCombinations.size()<<endl;
        for(auto i: allCombinations){
            for(auto j: i){
                cout<<j<<" ";
            }
            cout<<endl;
        }
    }
}