组合总和

问题：

Given a set of candidate numbers (C) (without duplicates) 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.
• 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]
]

解决：

① 结果要求返回所有符合要求解的题十有八九都是要利用到递归，而且解题的思路都大同小异，需要另写一个递归函数。注意是可以连续选择同一个数加入组合的。与方法②一样

class Solution { //17 ms
    public static List<List<Integer>> combinationSum(int[] candidates, int target){
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> cur = new ArrayList<>();
        dfs(candidates,0,target,cur,res);
        return res;
    }
    private static void dfs(int[] candidates, int i, int target, List<Integer> cur, List<List<Integer>> res) {//i表示当前遍历到的下标。
        if(target < 0)    return;
        if(target == 0){
            res.add(new ArrayList<>(cur));
            return;
        }
        for(int j = i; j < candidates.length && target >= candidates[j]; j ++){
            cur.add(candidates[j]);
            dfs(candidates,j,target - candidates[j],cur,res);//递归向后查找
            cur.remove(cur.size() - 1);//还原链表
        }
    }
}

② 简化

class Solution { //19ms
    List<List<Integer>> res = new ArrayList<>();  
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<Integer> cur = new ArrayList<>();
        dfs(candidates, 0, target, cur);
        return res;
    } 
    private void dfs(int[] nums, int i,int target, List<Integer> cur) {//i表示当前遍历到的位置
        if (target == 0) {
            res.add(new ArrayList<>(cur));
            // return;
        }    
        for (int j = i; j < nums.length; j ++) {
            if (nums[j] <= target) {
                cur.add(nums[j]);
                dfs(nums, j, target - nums[j], cur);
                cur.remove(cur.size() - 1);
            }
        }
    } 
}