Finding all combinations of numbers sum up to a number (Combination Sum II)

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination.
Note:

  • All numbers (including target) will be positive integers.
  • Elements in a combination (a_{1}, a_{2}, \dots ,a_{k}) must be in non-descending order. (i.e., a_{1} \leq a_{2} \leq \dots \leq a_{k}).
  • The solution set must not contain duplicate combinations.

INPUT: C = {10,1,2,7,6,1,5} and target = 8
OUTPUT: [1, 7], [1, 2, 5], [2, 6] and [1, 1, 6]

Thoughts:
This is similar to combination sum. We just need to start from the next element in the recursion.

Code (C++):

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        vector<int> partial;
        vector<vector<int> > sol;
        combSum2Recursion(num, target, partial, sol);
        return sol;
    }
    
    void combSum2Recursion(vector<int> &num, int target, vector<int> &partial,
        vector<vector<int> > &sol) {
        int sum = 0;
        for(int i = 0; i < partial.size(); ++i)
            sum += partial[i];
        if(sum == target) {
            if(find(sol.begin(), sol.end(), partial) == sol.end())
                sol.push_back(partial);
            return;
        } else if(sum > target) {
            return;
        } else {
            for(vector<int>::iterator itr = num.begin();
                    itr != num.end(); ++itr) {
                vector<int> partial_sol(partial);
                partial_sol.push_back(*itr);
                vector<int>::iterator start = itr;
                vector<int> remaining(++start, num.end());
                combSum2Recursion(remaining, target, partial_sol, sol);
            }
        }
    }
};

Code (Java):

import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
        combSumRecursion(num, target, new ArrayList<Integer>(), sol);
        return sol;
    }
    
    private void combSumRecursion(int[] num, int target, 
        ArrayList<Integer> partial, ArrayList<ArrayList<Integer>> sol) {
        int sum = 0;
        for(int i : partial)
            sum += i;
        if(sum == target) {
            if(!sol.contains(partial))
                sol.add(partial);
            return;
        } else if(sum > target) {
            return;
        } else {
            for(int i = 0; i < num.length; ++i) {
                int[] remaining = new int[num.length - 1 - i];
                System.arraycopy(num, i + 1, remaining, 0, remaining.length);
                ArrayList<Integer> partial_sol = new ArrayList<Integer>();
                partial_sol.addAll(partial);
                partial_sol.add(num[i]);
                combSumRecursion(remaining, target, partial_sol, sol);
            }
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: