TRENDING TOPICS
LEGAL
Cookie Settings
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, 42, 31, 1, 31, 2, 21, 1, 1, 21, 1, 1, 1, 1
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 targetprint 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, 1current_sum: 3, start: 1, result: [ 1,1,1 ]current_sum: 4, start: 2, result: [ 1,1,2 ]Add to output: 1, 1, 2current_sum: 3, start: 2, result: [ 1,2 ]current_sum: 4, start: 3, result: [ 1,3 ]Add to output: 1, 3current_sum: 2, start: 2, result: [ 2 ]current_sum: 4, start: 2, result: [ 2,2 ]Add to output: 2, 2current_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!
Free Resources
