You've successfully subscribed to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your billing info is updated.
Billing info update failed.

# 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);
}
}
``````
Algorithm

### Nicholas Wong

Fullstack software engineer with strong background in computer science and extensive experience in software engineering and architecture. Studied in NYU, worked in Yahoo, Rakuten and Manulife.