【Leetcode 热题 100】39. 组合总和

问题背景

给你一个 无重复元素 的整数数组 $candidates$ 和一个目标整数 $target$，找出 $candidates$ 中可以使数字和为目标数 $target$ 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
$candidates$ 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 $target$ 的不同组合数少于 $150$ 个。

数据约束

• $1\le candidates.length\le 30$
• $2\le candidates[i]\le 40$
• $candidates$ 的所有元素 互不相同
• $1\le target\le 40$

解题过程

题目叫组合总和，实际上是一个子集型的问题，有一点特殊是可以从原集合中取重复值。
由于结果的长度是不确定的，路径可以用列表来维护，递归的边界是找到正好相等的结果或者当前和大于目标和。
有一个剪枝的策略，对原数组进行排序，如果当前 $target$（实际上是已经去掉了之前轮次中所选数字之和的目标）小于下一个候选值 $candidate[i]$，那么这种情境下后续的所有选择都不可能成为答案了（排序后后面的后选值只会更大）。

这题还可以通过完全背包的视角，进行进一步预处理。
不过这部分基础知识学得并不是很好，暂时不要求掌握。

能应用排序是因为回溯是一种暴力解，回溯本身大概率会比排序耗时。

具体实现

选或不选

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 对候选数组进行排序，方便后面剪枝
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, path, res);
        return res;
    }
    
    private void dfs(int i, int target, int[] candidates, List<Integer> path, List<List<Integer>> res) {
        if(target == 0) {
            res.add(new ArrayList(path));
            return;
        }
        // 如果枚举到了数组越界位置或者剩余目标小于当前后选址，那么就不必往下递归了
        if(i == candidates.length || target < candidates[i]) {
            return;
        }
        // 不选当前值，那么递归到 i +  1，目标和 target 不变
        dfs(i + 1, target, candidates, path, res);
        // 选择当前值，加入到路径中，target 减少为 target - candidate[i]
        // 由于可以重复选择元素，递归的索引不变
        path.add(candidates[i]);
        dfs(i, target - candidates[i], candidates, path, res);
        // 注意恢复现场
        path.remove(path.size() - 1);
    }
}

选哪一个

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 对候选数组进行排序，方便后面剪枝
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        dfs(0, target, candidates, path, res);
        return res;
    }
    
    private void dfs(int i, int target, int[] candidates, List<Integer> path, List<List<Integer>> res) {
        if(target == 0) {
            res.add(new ArrayList(path));
            return;
        }
        // 如果枚举到了数组越界位置或者剩余目标小于当前后选址，那么就不必往下递归了
        if(target < candidates[i]) {
            return;
        }
        // j 从 i 开始枚举，不走回头路
        for(int j = i; j < candidates.length; j++) {
            // 尝试选择当前元素
            path.add(candidates[j]);
            dfs(j, target - candidates[j], candidates, path, res);
            // 恢复现场
            path.remove(path.size() - 1);
        }
    }
}