Given a positive integer, `target`

, print all possible combinations of positive integers that sum up to the `target`

number.

For example, if we are given input ‘5’, these are the possible sum combinations.

```
1, 4
2, 3
1, 1, 3
1, 2, 2
1, 1, 1, 2
1, 1, 1, 1, 1
```

The output will be in the form a list of lists or an array of arrays. Each element in the list will be another list containing a possible sum combination.

- Recursion
- Two lists

vector<vector<int>> print_all_sum(int target){vector<vector<int>> output;//Write - Your - Codereturn output;}

void print(vector<vector<int>> output){for(int i = 0; i < output.size(); i++){cout << "[ ";for(int j = 0; j < output[i].size(); j++){cout << output[i][j] << ", ";}cout << "]" << endl;}}void print_all_sum_rec(int target,int current_sum,int start, vector<vector<int>>& output,vector<int>& result) {if (target == current_sum) {output.push_back(result);}for (int i = start; i < target; ++i) {int temp_sum = current_sum + i;if (temp_sum <= target) {result.push_back(i);print_all_sum_rec(target, temp_sum, i, output, result);result.pop_back();} else {return;}}}vector<vector<int>> print_all_sum(int target) {vector<vector<int>> output;vector<int> result;print_all_sum_rec(target, 0, 1, output, result);return output;}int main(int argc, const char* argv[]) {int n = 4;vector<vector<int>> result = print_all_sum(n);print (result);}

Exponential.

Linear, O(n).

Here we will recursively go through all possible sum combinations. Whenever the running sum equals the target, we will print that combination.

The algorithm will recursively check all the numbers which can sum up to the `target`

. In each recursive call, there is a `for`

loop which runs from `start`

to `target`

. `start`

is initially `1`

. The `current_sum`

is the variable that is incremented in every recursive call.

Here is the logic of the code; every time a value is added to the `current_sum`

, it is also added to the `result`

list which is the sum combination for that particular call. Whenever `current_sum`

becomes equal to `target`

, we can be sure that the `result`

list contains a possible combination for `target`

. This list is appended to the final `output`

list.

```
Base condition of recursion:
if current_sum equals target
print the output contents
```

Before each recursive call, an element is added to `result`

. However, after each call, this element is also removed from the list in order to reset the list.

Let’s run this algorithm step-by-step for an example where we have to find all possible sum combinations of `4`

.

```
current_sum: 0, start: 1, result: [ ]
current_sum: 1, start: 1, result: [ 1 ]
current_sum: 2, start: 1, result: [ 1,1 ]
current_sum: 3, start: 1, result: [ 1,1,1 ]
current_sum: 4, start: 1, result: [ 1,1,1,1 ]
Add to output: 1, 1, 1, 1
current_sum: 3, start: 1, result: [ 1,1,1 ]
current_sum: 4, start: 2, result: [ 1,1,2 ]
Add to output: 1, 1, 2
current_sum: 3, start: 2, result: [ 1,2 ]
current_sum: 4, start: 3, result: [ 1,3 ]
Add to output: 1, 3
current_sum: 2, start: 2, result: [ 2 ]
current_sum: 4, start: 2, result: [ 2,2 ]
Add to output: 2, 2
current_sum: 3, start: 3, result: [ ]
```

Practice problems like this and many more by checking out our Grokking the Coding Interview: Patterns for Coding Questions course!

TRENDING TOPICS