# Summing Combinations

## Question

Given a integers m and n, generate all combination within 1 to n that would give the sum m. For example, for `m=5`

and `n=5`

, the combinations are `{5}`

, `{4+1}`

, `{3+2}`

.

## Solution

This is a knapsack problem.

```
#knapsack that store the found combination
knapsack = array
# find combination of 1..n with sum target
find_combination(target, n)
if target <= 0 or n <= 0 then return
if target == n then found()
# put n to knapsack, find combination involves n
push n to knapsack
remain = target - n
find_combination(remain, n-1)
# remove n from knapsack, find combination involves n-1
pop knapsack
find combination(target, n-1)
```

## Sample

```
# knapsack that store the found combination
knapsack = []
# what to do with found combination in knapsack
def found(n):
for number in knapsack: print "%d +" % number,
print n
# find combination
def find_combination(target, n):
if n <= 0 or target <= 0: return
if n == target: found(n)
# find combinations with n
knapsack.append(n)
find_combination(target - n, n - 1)
# find combinations without n
knapsack.pop()
find_combination(target, n - 1)
# find combination of 25 with 1..20
find_combination(25, 20)
```

```
#include <iostream>
#include <list>
using namespace std;
list < int > knapsack;
void found(int n) { // reverse print
for (list < int > ::const_iterator item = knapsack.begin(); item != knapsack.end(); item++) printf("%d + ", * item);
printf("%dn", n);
}
void find_combination(int target, int n) {
if (n <= 0 || target <= 0) return;
if (n == target) found(n);
knapsack.push_back(n);
find_combination(target - n, n - 1);
knapsack.pop_back();
find_combination(target, n - 1);
}
int main() {
find_combination(25, 20);
}
```

```
import java.util.Stack;
public class InterviewPractice21 {
private static Stack < Integer > snapsack = new Stack < Integer > ();
private static void found(int n) {
for (int item: snapsack) System.out.printf("%d + ", item);
System.out.printf("%dn", n);
}
private static void find_combination(int target, int n) {
if (target <= 0 || n <= 0) return;
if (n == target) found(n);
snapsack.push(n);
find_combination(target - n, n - 1);
snapsack.pop();
find_combination(target, n - 1);
}
public static void main(String[] args) {
find_combination(25, 20);
}
}
```

### Nicholas Workshop Newsletter

Join the newsletter to receive the latest updates in your inbox.