Coderust: Hacking the Coding Interview/

...

/

All Possible Combinations for a Given Sum

All Possible Combinations for a Given Sum

Given a positive integer as target, print all the possible combinations of positive integers that sum to the target number.

We'll cover the following...

Statement

Given a positive integer as the target, print all the possible combinations of positive integers that sum to the target number.

Example

Sample input

4

Expected output

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

Try it yourself

#include <vector>
#include <iostream>
using namespace std;
vector<vector<int>> PrintAllSum(int target){
	vector<vector<int>> output;
	//Write - Your - Code
	return output;
}

Solution

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, the start is initially 1.
  • The current sum 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
...