Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

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

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

Output:

```
[
[3],
[1, 2]
]
```

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

Output:

```
[
[1, 1]
]
```

- 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^{n}. 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.

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^{n} 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.

O(n * 2^{n}).

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^{n}) 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.

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.

O(n * 2^{n}).

Space used for input: O(n).

Auxiliary space used: O(n).

Space used for output: O(n * 2^{n}).

So, total space complexity: O(n * 2^{n}).

```
/*
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> ¤t,
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;
}
```

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).

- Now, we will consider the two possibilities of excluding/including the current element

- Loop through the

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
- 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.

O(n * 2^{n}).

To build the `dp`

table: O(n * target).

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

O(n * 2^{n}).

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^{n}).

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

To store all of these combinations in the `combination_set`

: O(n * 2^{n}).

O(n * 2^{n}).

Space used for input: O(n).

Auxiliary space used: O(n * 2^{n}).

Space used for output: O(n * 2^{n}).

So, total space complexity: O(n * 2^{n}).

```
/*
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.

Note: Input and Output will already be taken care of.