Search⌘ K
AI Features
Home
Courses
Coderust: Hacking the Coding Interview

All Possible Combinations for a Given Sum

Explore how to recursively find all combinations of positive integers that add up to a given target sum. This lesson guides you through the algorithm, explaining the step-by-step process and the use of recursion with backtracking. You will understand the time and space complexities involved, helping you strengthen your problem-solving skills in mathematical coding challenges.

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
...