Find All Sum Combinations

Problem Statement

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.

Hint

Recursion
Two lists

Try it yourself

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);
}

Solution Explanation

Runtime Complexity

Exponential.

Memory Complexity

Linear, O(n).

Solution Breakdown

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: [ ]

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments