Interview Practice 21 - 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); } }
Show Comments