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 particular call.
  • Whenever the current sum becomes equal to the target, we can be sure that the result list contains a possible combination for the 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 the result, however, after each call, this element is also removed from the list to reset the list.

Let’s run this algorithm step-by-step for an example where we’ll 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: [] 

#include <string>
#include <vector>
#include <iostream>
using namespace std;
void PrintAllSumRec(int target, int current_sum, int start, vector<int>& result,
					vector<vector<int>>& output) {
	// If current sum is equal to target, shallow copy the result into ouput array
	if (target == current_sum) {
		output.push_back(result);
	}
	for (int i = start; i < target; ++i) {
		// Increment sum in each recursive call
		int temp_sum = current_sum + i;
		// If current sum is equal or less than target,
		// push it in result array and call function recursively
		if (temp_sum <= target) {
			result.push_back(i);
			PrintAllSumRec(target, temp_sum, i, result, output);
			result.pop_back();
		} else {
			return;
		}
	}
}
vector<vector<int>> PrintAllSum(int target) {
	vector<vector<int>> output;
	vector<int> result;
	PrintAllSumRec(target, 0, 1, result, output);
	return output;
}
int main() {
	vector<int> n = {2, 3, 4};
	for (int i = 0; i < n.size(); i++) {
		vector<vector<int>> result = PrintAllSum(n[i]);
		cout << i + 1 << ". All sum combinations of " << n[i] << ": ";
		// A custom function to print the vector
		PrintListOfLists(result);
    cout << "\n------------------------------------------------------------------------------------------------------\n" << endl;
	}
}

Time complexity

Though the detailed proof lies outside the scope of this course, we observe that the cost for a given nn is the summation of the costs of finding the combinations for n−1n-1, n−2n-2, and so on to 33 ...