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] 

Solution: recursion
基本思路是先排好序，然后每次递归中把剩下的元素一一加到结果集合中，并且把目标减去加入的元素，然后把剩下元素（包括当前加入的元素）放到下一层递归中解决子问题。算法复杂度因为是NP问题，所以自然是指数量级的。

注意在实现中for循环中第一步有一个判断，那个是为了去除重复元素产生重复结果的影响，因为在这里每个数可以重复使用，所以重复的元素也就没有作用了，所以应该跳过那层递归。

public class Solution {
    public ArrayList> combinationSum(int[] candidates, int target) {
        ArrayList> result = new ArrayList>();
        if(candidates == null || candidates.length == 0)
            return result;
        
        Arrays.sort(candidates);  //sort the candidates first
        int start = 0;
        ArrayList list = new ArrayList();
        select(candidates, target, start, list, result);
        return result;
    }
    
    public void select(int[] candidates, int target, int start, ArrayList list, ArrayList> result) {
        if(target < 0)
            return;
        if(target == 0) {
            result.add(new ArrayList (list));
            return;
        }
        for(int i = start; i < candidates.length; i++) {
            if(i > 0 && candidates[i] == candidates[i - 1])
                continue;
            
            list.add(candidates[i]);
            select(candidates, target-candidates[i], i, list, result);
            list.remove(list.size() - 1);
        }
    }
}