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.

For example, given candidate set 2,3,6,7 and target 7

A solution set is:

[7]

[2, 2, 3]

This algorithm has time complexity O((n+k)!)

where n is the size of candidates, and k is the max repeated times for each candidates

and space complexity O(m) where m is the size of array for the solution.

public class Solution {
    List<List<Integer>> output = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        helper(candidates, 0, target, new ArrayList());
        return output;
    }

    private void helper(int[] array, int start, int target, List<Integer> result) {
        if (target == 0) {
            output.add(new ArrayList(result));
            return;
        } else if (target < 0) {
            return;
        } else {
            for (int i = start; i < array.length; i++) {
                if (target < array[i]) {
                    return;
                }
                result.add(array[i]);
                helper(array, i, target-array[i], result);
                result.remove(result.size() - 1);               
            }
        }
    }
}

Follow up:

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.

public class Solution {
    List<List<Integer>> output = new ArrayList<List<Integer>>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        helper(candidates, 0, target, new ArrayList());
        Set<List<Integer>> set = new HashSet<List<Integer>>(output);
        output.clear();
        output.addAll(set);

        return output;
    }

    private void helper(int[] array, int start, int target, List<Integer> result) {

        if (target == 0) {
            output.add(new ArrayList(result));
            return;
        } else if (target < 0) {
            return;
        } else {

            for (int i = start; i < array.length; i++) {

                if (target < array[i]) {
                    return;
                }
                result.add(array[i]);
                helper(array, i + 1, target-array[i], result);
                result.remove(result.size() - 1);               
            }
        }
    }
}