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]
]
Constraints:
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 2n. 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 2n 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
:
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.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 2k) possibilities to include that element in a combination. The possibilities are as follows:
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 * 2n).
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(2n) 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 * 2n).
Space used for input: O(n).
Auxiliary space used: O(n).
Space used for output: O(n * 2n).
So, total space complexity: O(n * 2n).
/*
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:
arr[0 … i]
that sums up to j
.Our approach for building this table will be:
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.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]
.i
from i
= 1 to n - 1
:
local_target
from local_target = target
to 0 (in reverse):
arr[i]
in any subset. 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:
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.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. combinations_set
and return.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.arr_index < 0
: It means that no element is now left to be considered. Thus, we will return.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.arr[arr_index]
from the current subset or to include it in the current subset. 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 * 2n).
To build the dp
table: O(n * target).
To recursively find the combinations: O(n * 2n). (The upper limit for the total number of combinations will be O(2n). Generating and inserting each of these combinations in the set will be O(n)).
O(n * 2n).
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(2n).
The upper limit for the size of each combination: O(n).
To store all of these combinations in the combination_set
: O(n * 2n).
O(n * 2n).
Space used for input: O(n).
Auxiliary space used: O(n * 2n).
Space used for output: O(n * 2n).
So, total space complexity: O(n * 2n).
/*
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:
To learn more, register for the FREE webinar.
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]
]
Constraints:
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 2n. 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 2n 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
:
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.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 2k) possibilities to include that element in a combination. The possibilities are as follows:
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 * 2n).
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(2n) 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 * 2n).
Space used for input: O(n).
Auxiliary space used: O(n).
Space used for output: O(n * 2n).
So, total space complexity: O(n * 2n).
/*
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:
arr[0 … i]
that sums up to j
.Our approach for building this table will be:
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.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]
.i
from i
= 1 to n - 1
:
local_target
from local_target = target
to 0 (in reverse):
arr[i]
in any subset. 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:
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.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. combinations_set
and return.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.arr_index < 0
: It means that no element is now left to be considered. Thus, we will return.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.arr[arr_index]
from the current subset or to include it in the current subset. 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 * 2n).
To build the dp
table: O(n * target).
To recursively find the combinations: O(n * 2n). (The upper limit for the total number of combinations will be O(2n). Generating and inserting each of these combinations in the set will be O(n)).
O(n * 2n).
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(2n).
The upper limit for the size of each combination: O(n).
To store all of these combinations in the combination_set
: O(n * 2n).
O(n * 2n).
Space used for input: O(n).
Auxiliary space used: O(n * 2n).
Space used for output: O(n * 2n).
So, total space complexity: O(n * 2n).
/*
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:
To learn more, register for the FREE webinar.
Attend our free webinar to amp up your career and get the salary you deserve.