Generate All Combinations With Sum Equal To Target Problem Statement

Given an integer array, generate all the unique combinations of the array numbers that sum up to a given target value.

Example One

{
"arr": [1, 2, 3],
"target": 3
}

Output:

[
[3],
[1, 2]
]

Example Two

{
"arr": [1, 1, 1, 1],
"target": 2
}

Output:

[
[1, 1]
]

Notes

• Each number in the array can be used exactly once.
• All the returned combinations must be different. Two combinations are considered different if their sorted version is different.
• The order of combinations and the order of the numbers inside a combination does not matter.

Constraints:

• 1 <= size of the input array <= 25
• 1 <= value in the array <= 100
• 1 <= target value <= 2500

We have provided two solutions.

Throughout this editorial, we will refer to the input array as arr, its size as n and the target number as target.

One brute force that you might come up with is to first generate all the possible combinations of the input array and then filter out the unique combinations with sum equal to target. The total number of combinations that will be formed using this approach will be 2ⁿ. We will then discard all the combinations that do not have the sum equal to target. Finally, we will store the sorted version of each combination with sum equal to target in an unordered set to get all the unique combinations.

Note that this approach generates a lot of invalid combinations that we do not even require. So let us look at an approach that will carefully generate the combination so that the final filtering is not needed.

Generate All Combinations With Sum Equal To Target Solution 1: Backtracking With Pruning

For any number present in the array, we have two possibilities to consider. Either we can include the number in a given combination or we can ignore it. This way, we will have 2ⁿ number of combinations generated.

But, here are a few observations using which we can avoid generating a lot of combinations that do not sum up to the target:

• The numbers inside the array and the target are positive integers. Therefore, if the sum of a combination exceeds the value of the target, we no longer need to recurse further with this combination.
• We need a way so that the duplicate combinations are not generated. Assume that there are say, k occurrences of an element num in the array at indices ind1, ind2 ... indk. Here, taking ind1 in a combination and excluding ind2 ... indk is exactly the same as taking ind2 and excluding ind1, ind3 ... indk. This is where we need to be careful while generating the unique combinations. If any element occurs k times in the array, then there are at-most k + 1 (and not 2^k) possibilities to include that element in a combination. The possibilities are as follows:
  • Do not include it.
  • Include only one occurrence of that element.
  • Include only two occurrences of that element.
    ….
  • Include k occurrences of that element.

Using these observations, we can generate all the unique combinations that sum up to the given target.

Note that this approach requires us to have a list of indices where a particular element occurs. Instead of separately storing these lists, we will be sorting the array initially so that all the occurrences of any value come together in the array. This way it will be easier to track the occurrences.

Time Complexity

O(n * 2ⁿ).

In the worst case, we might have all the unique elements in the array. In that case, we will have exactly two possibilities for each of the n elements. Therefore, the number of unique combinations will be O(2ⁿ) and as we find a combination, we push it into our resultant array. This step takes O(n) amount of time in the worst case.

Auxiliary Space Used

O(n).

The maximum number of recursive stacks at any moment in time can be equal to the number of unique elements present in the array. The number of unique elements will be O(n) in the worst case.

Space Complexity

O(n * 2ⁿ).

Space used for input: O(n).

Auxiliary space used: O(n).

Space used for output: O(n * 2ⁿ).

So, total space complexity: O(n * 2ⁿ).

Code For Generate All Combinations With Sum Equal To Target Solution 1: Backtracking With Pruning

/*
Asymptotic complexity in terms of the size of `arr` `n`:
* Time: O(n * 2^n).
* Auxiliary space: O(n).
* Total space: O(n * 2^n).
*/

void get_combinations(vector<int> &arr, int index, int target, vector<int> &current,
                      vector<vector<int>> &combinations) {
    if (target == 0) {
        combinations.push_back(current);
        return;
    }

    if (index == arr.size() or target < 0) {
        return;
    }

    // arr[index] is in index range [index, end).
    int end = index;
    while (end < arr.size() and arr[end] == arr[index]) {
        end++;
    }

    // Skipping the current element.
    get_combinations(arr, end, target, current, combinations);

    // Current element can be present 1, 2 .... (end - index) number of times in a combination.
    int count = 1;
    while (count <= end - index) {
        current.push_back(arr[index]);
        get_combinations(arr, end, target - count * arr[index], current, combinations);
        count++;
    }

    // Backtrack to convert the vector "current" back to its previous state.
    count = 1;
    while (count <= end - index) {
        current.pop_back();
        count++;
    }
}

vector<vector<int>> generate_all_combinations(vector<int> &arr, int target) {
    vector<vector<int>> combinations;
    vector<int> current;

    sort(arr.begin(), arr.end());

    get_combinations(arr, 0, target, current, combinations);

    return combinations;
}

Generate All Combinations With Sum Equal To Target Solution 2: Dp With Pruning

In this solution, we will first construct a Boolean two-dimensional dp-table where the value dp[i][j] will be:

• True: If there exists a way to pick a subset arr[0 … i] that sums up to j.
• False: Otherwise.

Our approach for building this table will be:

• Sort the array. The reason for sorting will get more clear in the later part of this editorial.
• Create a two-dimensional Boolean array called dp with dimensions n * (target + 1) and set all of its values to false. The purpose of having this table has already been described above.
• Initiate dp[0][0] and dp[0][arr[0]] = true. This is to indicate that there exists a subset of { arr[0] } that can sum up to both 0 and arr[0].
• Loop through i from i = 1 to n - 1:
  • Loop through the local_target from local_target = target to 0 (in reverse):
    • Now, we will consider the two possibilities of excluding/including the current element arr[i] in any subset.
      Considering the “excluding” case, we will first set dp[i][local_target] to true only if dp[i - 1][local_target] is true.
      Next, consider the “including” case, we will check if dp[i - 1][local_target] is true. If it is, then we will set dp[i][local_target + arr[i]] to true (if it falls in the valid range of our dp-table).

After the termination of the above process, our dp table will be built completely. Therefore, our next step will be to generate all of the valid combinations from the array in an optimized manner. To do this, we will follow a recursive process which will one-by-one consider the possibility of including/excluding each element from the current subset. If at any moment, the subset sums up to the target value, we will insert it into our result.

But note that, since the array might contain duplicate elements, we might end up generating some duplicate subsets that sum up to the target. To avoid this, we will not directly insert the subsets into our result. Rather, we will keep inserting the subsets in a set data-structure to avoid having the duplicate subsets in our result (this set will be shared among all of the recursive calls). This was basically the reason why we will have to sort the array at the starting of this solution (as two or more same subsets might otherwise get inserted in our set in different orders).

Overall, the recursive process that we will be following is:

• Initiate a helper function which takes the array arr[], integers arr_index, current_sum, target, mask, the dp[][] table and the resultant set called combinations_set as its inputs. The purpose of some of these parameters have been described below:
  • arr_index: This will denote the current index in the array that we are considering. Initially, this will be equal to n - 1.
  • current_sum: This will denote the sum of the current subset that we are considering. Initially, this will be equal to 0.
  • mask: This will keep track of which numbers have been included in the current subset. If the i-th bit from left is set in the mask, then it means that the element arr[i] exists in the current subset. Otherwise, it does not. Initially, this will be equal to 0 as no element has currently been considered.
• Next, we will check for the following base-conditions:
  • If current_sum equals target: In this case, we have successfully found a combination with the target sum. Therefore, we will build the current combination by iterating through the array from i = 0 to n - 1. During any iteration, if the i-th bit is set in the mask, then we will append arr[i] in the current combination. Else, we will skip it.
    Finally, we will insert the current combination in the combinations_set and return.
  • If current_sum > target: Since the values of the array are positive, it is not possible to build the target sum with the current set of elements. Thus, we will return.
  • If arr_index < 0: It means that no element is now left to be considered. Thus, we will return.
  • If dp[arr_index][target - current_sum] is false: It means that there exists no subset of arr[0 … arr_index] that sums up to target - current_sum. Thus, we will return in this case as well.
• If all of the above conditions fail, then we will be left with two possibilities: Either to exclude arr[arr_index] from the current subset or to include it in the current subset.
  To consider both of these possibilities, we will initiate two child processes.
  For the child process that considers the “excluding” case, we will pass: arr_index as arr_index - 1.
  For the child process that consider the “including” case, we will pass: arr_index as arr_index - 1, current_sum as current_sum + arr[arr_index], mask as (mask | (1 << arr_index)) (setting the i-th bit of the mask).

After the termination of the recursive process, we will iterate through the combinations_set and insert each of the combinations into our result and return it.

Time Complexity

O(n * 2ⁿ).

To build the dp table: O(n * target).

To recursively find the combinations: O(n * 2ⁿ). (The upper limit for the total number of combinations will be O(2ⁿ). Generating and inserting each of these combinations in the set will be O(n)).

Auxiliary Space Used

O(n * 2ⁿ).

For the dp table: O(n * target).

Maximum number of recursive calls in the call stack: O(n).

The upper limit for the total number of combinations: O(2ⁿ).

The upper limit for the size of each combination: O(n).

To store all of these combinations in the combination_set: O(n * 2ⁿ).

Space Complexity

O(n * 2ⁿ).

Space used for input: O(n).

Auxiliary space used: O(n * 2ⁿ).

Space used for output: O(n * 2ⁿ).

So, total space complexity: O(n * 2ⁿ).

Code For Generate All Combinations With Sum Equal To Target Solution 2: Dp With Pruning

/*
Asymptotic complexity in terms of the size of `arr` `n`:
* Time: O(n * 2^n).
* Auxiliary space: O(n * 2^n).
* Total space: O(n * 2^n).
*/

// This function will recursively generate all of the combinations that sum up to the target
// and insert them into the combinations_set.
// It will also prune the branches *using the dp-table) which are guaranteed to not generate a
// valid combination.
void generate_all_combinations_helper(vector<int> &arr, int arr_index, int current_sum,
                                      int target, int mask, vector < vector < bool >> &dp,
                                      set<vector<int>> &combinations_set) {

    if (current_sum == target) {
        vector<int> combination;
        for (int i = 0; i < arr.size(); i++) {
            if (mask & (1 << i)) {
                combination.push_back(arr[i]);
            }
        }

        combinations_set.insert(combination);
        return;
    }

    if (current_sum > target) {
        return;
    }
    if (arr_index < 0) {
        return;
    }
    if (dp[arr_index][target - current_sum] == false) { // Pruning the current branch.
        return;
    }

    generate_all_combinations_helper(arr, arr_index - 1, current_sum, target, mask, dp, combinations_set);
    generate_all_combinations_helper(arr, arr_index - 1, current_sum + arr[arr_index], target,
                                     (mask | (1 << arr_index)), dp, combinations_set);
}

vector<vector<int>> generate_all_combinations(vector<int> &arr, int target) {
    sort(arr.begin(), arr.end());

    vector < vector < bool > > dp(arr.size(), vector < bool > (target + 1, false));

    // dp[i][j] = 1 if there exists a way to make a sum equal to j using the first i+1 elements.
    //          = 0 otherwise

    dp[0][0] = true;
    dp[0][arr[0]] = true;
    for (int i = 1; i < arr.size(); i++) {
        for (int local_target = target; local_target >= 0; local_target--) {
            dp[i][local_target] = dp[i - 1][local_target];

            if (dp[i - 1][local_target] and local_target + arr[i] < dp[i].size()) {
                dp[i][local_target + arr[i]] = true;
            }
        }
    }

    set<vector<int>> combinations_set;
    generate_all_combinations_helper(arr, arr.size() - 1, 0, target, 0, dp, combinations_set);

    vector<vector<int>> result;
    for (auto combination : combinations_set) {
        result.push_back(combination);
    }

    return result;
}

We hope that these solutions to combinational sum problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

• Back-end Engineering Interview Course
• Front-end Engineering Interview Course
• Full Stack Developer Interview Course

‍To learn more, register for the FREE webinar.