Leetcode: 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 (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] 

Understand the problem:
The problem asks for finding all unique combinations where the candidate numbers sums to the target. Note that same number can be used with unlimited number of times. There are also several special requirements in the problem. There are no negative numbers in the list, and the output should be in non-descending order. In addition, the solution set must not contain duplicate combinations. 

Solution:
This question could be categorized into permutation and combination problem, where DFS should be used to produce the solution. 

Code (Java):

public class Solution {
    public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if (candidates == null || candidates.length == 0) {
            return result;
        }
        
        Arrays.sort(candidates);
        
        combinationSumHelper(candidates, target, 0, new ArrayList<Integer>(), 0, result);
        
        return result;
    }
    
    private void combinationSumHelper(int[] candidates, int target, int sum, 
　　　　　ArrayList<Integer> curr, int start, ArrayList<ArrayList<Integer>> result) {
        if (sum == target) {
            result.add(new ArrayList<Integer>(curr));
            return;
        }
        
        if (sum > target) {
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;
            sum += candidates[i];
            curr.add(candidates[i]);
            
            combinationSumHelper(candidates, target, sum, curr, i, result);
            
            sum -= candidates[i];
            curr.remove(curr.size() - 1);
        }
    }
}

Discussion:
The time complexity for this question is exponential, since it is a NP problem. 

Summary:
This problem can be categorized into permutation and combination problems. Using the DFS is the key to solution. Draw a recursion tree will also help at understanding the idea as well.