Find All Sum Combinations

Home/

Blog/

1 min read

Oct 15, 2025

Content

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown

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.

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