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);
    }
}