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

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times.
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 = {2,3,6,7} and target = 7
OUTPUT: [7] and [2, 2, 3]

Thoughts:
We should use recursion combined with backtracking. We try to add one more element to the partial solution each time, if we have reached the sum, we add that partial solution to the solution list. If we have exceed the sum, we disregard that partial solution. If we have not reached the sum, we recursively add more elements to the partial solution.

Code (C++):

class Solution {
public:
    vector<vector<int> > combinationSum(vector<int> &candidates, 
            int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int> > solutions;
        vector<int> partial;
        combSumRecursion(candidates, target, partial, solutions);
        return solutions;
    }
    
    void combSumRecursion(vector<int> &candidates, int target, 
            vector<int>& partial, vector<vector<int> >& solutions) {
        int sum = 0;
        for(int i = 0; i < partial.size(); ++i)
            sum += partial[i];
        if(sum == target) {
            solutions.push_back(partial);
            return;
        } else if(sum > target) {
            return;
        } else {
            for(int i = 0; i < candidates.size() 
                            && candidates[i] < target; ++i) {
                vector<int> partial_sol(partial);
                partial_sol.push_back(candidates[i]);
                vector<int> remaining;
                for(int j = i; j < candidates.size(); ++j)
                    remaining.push_back(candidates[j]);
                combSumRecursion(remaining, target, 
                    partial_sol, solutions);
            }
        }
    }
};

Code (Java):

import java.util.Arrays;
import java.util.ArrayList;
public class Solution {
    public static ArrayList<ArrayList<Integer>> 
            combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> sol = 
                new ArrayList<ArrayList<Integer>>();
        Arrays.sort(candidates);
        combSumRec(candidates, target, 
                new ArrayList<Integer>(), sol);
        return sol;
    }
    
    private static void combSumRec(int[] candidates, 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 < candidates.length; ++i) {
                ArrayList<Integer> partial_sol = 
                        new ArrayList<Integer>();
                partial_sol.addAll(partial);
                partial_sol.add(candidates[i]);
                int[] remaining = new int[candidates.length - i ];
                System.arraycopy(candidates, i, 
                    remaining, 0, remaining.length);
                combSumRec(remaining, target, 
                    partial_sol, sol);
            }
        }
    }
}
Advertisements

1 Comment (+add yours?)

  1. Trackback: Finding all combinations of numbers sum up to a number (Combination Sum II) « Runhe Tian Coding Practice

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: