Combination Sum - Leetcode

combinationSum.java

/*
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 (a1, a2, ..., ak) must be in non-descending order. (ie, a1 ? a2 ? ... ? ak).
The solution set must not contain duplicate combinations.
For example, given candidate set 2,3,6,7 and target 7, 
A solution set is: 
[7] 
[2, 2, 3]

Algorithm:
Basically find out the combination of the int array to sum up to the target and 
it needs to take care of the repeated number, such as [2,2,3] and [1,6] for 7

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 {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(candidates.length == 0) return ret;
        Arrays.sort(candidates);
        
        combinationSumHelper(candidates, target, 0, 0, ret, list);
        
        return ret;
    }
    
    public void combinationSumHelper(int[] input, int target, int start, int sum,
                                    ArrayList<ArrayList<Integer>> ret,
                                    ArrayList<Integer> list) {
        if(sum > target) return;// Note: This method cannot finish large set if this line is missing
        for(int i = start; i < input.length; i++) {
            list.add(input[i]);
            sum += input[i];
            if(sum == target) {
                ret.add(new ArrayList<Integer>(list));
                sum -= list.get(list.size() - 1);
                list.remove(list.size() - 1);
                return;
            }

            if(sum < target) {
                combinationSumHelper(input, target, i, sum, ret, list);
            } else {
                combinationSumHelper(input, target, i+1, sum, ret, list);
            }

            sum -= list.get(list.size() - 1);
            list.remove(list.size() - 1);
        }
        
        return;
    }
}

Great solution, removed redundancy from your code - https://gist.github.com/Buzz-Lightyear/85aab6e372423d025e91

Why do we use depth first search here? As in when I read this problem, how would i know DFS is the way to approach it?

@aoben10 : Here we need all the combinations that result in the target. Another approach would have been using Dynamic Programming if we were asked for say the best result. Using DFS, we are making sure of scanning every element. Note repetitions are allowed, so we are scanning every candidate element again and again until the sum exceeds the target.

What if repetitions are not allowed? Is there any way to limit the number of elements required for the combinational sum?