You've successfully subscribed to Nicholas Workshop
Great! Next, complete checkout for full access to Nicholas Workshop
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

Summing Combinations

Nicholas Wong
Nicholas Wong

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.