java递归 对应LeetCode39 40题目

1. 排序 当数组之和大于target时候 跳出
2. 递归中的判断条件（跳出递归的条件）
3. 是否取当前数字（注意可以重复即取了之后 index不变，不取当前数字可以直接递归调用 index+1）

看代码：

class Solution {
    List<List<Integer>> res = new LinkedList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        LinkedList<Integer> list = new LinkedList<>();
        dfs(candidates, target, 0, res, list);
        return res;
    }

    private void dfs(int[] candidates, int target, int idx, List<List<Integer>> res, LinkedList<Integer> list) {

        if (target == 0) {
            res.add(new ArrayList<>(list));
            return;
        }
        if (idx == candidates.length) {
            return;
        }


        // 跳过当前数字
        dfs(candidates, target, idx + 1, res, list);
        // 选择当前数
        if (target - candidates[idx] >= 0) {
            list.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], idx, res, list);
            list.removeLast();
        }
    }
}

LeetCode40题：

**注意：**结果集不重复，数字不可重复使用，数组中有重复数字

1. 对数组排序方便以后操作
2. 计算数组中每个数字出现次数
3. 写递归方法
4. 跳出递归条件（target==0、index=length（遍历完了）、结果数组相加大于target）
5. 递归操作：跳过当前数字（index+1）；不跳过（判断可以添加几个当前数字，最后去掉添加上的元素）