组合总和

组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

思路：针对候选数组，每次可以有三种操作：

• 选取一个继续下一个
• 选取后不往下走（可重复选取）
• 不选取往下走

经分析，发现第一个操作的结果会背后两个操作包含，所以只需要考虑后两种即可

代码：

class Solution {
    List<List<Integer>> rsl = new ArrayList();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<Integer> path = new ArrayList();
        find(candidates, 0, target, path);
        return rsl;
    }

    public void find(int[] candidates, int idx, int target, List<Integer> path){
        if(target < 0) {
            return;
        }
        if(target == 0) {
            rsl.add(new ArrayList(path));
            return;
        }
        if(idx > candidates.length - 1) {
            return;
        }
        int cur = candidates[idx];
        // 拿了往下走，被包含所以不用做
        // path.add(cur);
        // find(candidates, idx+1, target - cur, path);
        // path.remove(path.size()-1);

        // 拿了原地不动
        path.add(cur);
        find(candidates, idx, target - cur, path);
        path.remove(path.size()-1);

        // 不拿往下走
        find(candidates, idx+1, target, path);
    }
}