标签： 回溯

目标

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字1到9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

说明:

• 2 <= k <= 9
• 1 <= n <= 60

思路

从1~9中选k个，使它们的和是n。暴力求解需要 C9k 次遍历，可以使用回溯算法成批地考察具有特定前缀的所有候选解，一旦发现与目标解不合，需要撤销当前选择返回上一层进行下一个可能的尝试。dfs只是回溯算法的一环。关于回溯算法具体可参考《数据结构与算法分析》第314页。

代码

/**
 * @date 2024-04-21 20:44
 */
public class CombinationSum216 {

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= 9; i++) {
            dfs(k - 1, i, n, q, res);
        }
        return res;
    }

    public void dfs(int k, int root, int target, Deque<Integer> q, List<List<Integer>> res) {
        if (k < 0 || target < 0) {
            return;
        }
        if (target == root && k == 0) {
            q.offer(root);
            res.add(new ArrayList<>(q));
            q.pollLast();
            return;
        }
        q.offer(root);
        for (int i = root + 1; i <= 9; i++) {
            dfs(k - 1, i, target - root, q, res);
        }
        q.pollLast();
    }
}

性能

目标

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

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

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

示例 1：

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

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

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

思路

一看到这道题就想到要用动态规划，但是昨天看了回溯算法的视频，所以就试图使用dfs去写。

先从target开始，循环减去可选数字，然后递归。想法是好的，但是这种集合嵌套集合的操作一会就把我搞晕了，向下传递什么，返回什么？有机会再想想吧。

还是用动态规划吧，难点在于去重。刚开始甚至写了hash函数，但是它不能处理2, 5（2 3） 与 4（2 2）, 3的情况，dp[2] + dp[5] 与 dp[4] + dp[3] 得到的组合是相同的 [2, 2, 3]。

这让我想到了518.零钱兑换II，这两道题本质是一样的。那个只让返回组合数，这个需要返回具体的组合。

去重的精髓就在于不能提前初始化dp，只能在第一次访问到候选值的时候初始化。

代码

/**
 * @date 2024-04-20 10:20
 */
public class CombinationSum39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>>[] dp = new List[target + 1];
        for (int i = 0; i <= target; i++) {
            dp[i] = new ArrayList<>();
        }
        for (int candidate : candidates) {
            if (candidate <= target) {
                List<Integer> list = new ArrayList<>();
                list.add(candidate);
                dp[candidate].add(list);
            }
            for (int i = candidate; i <= target; i++) {
                for (List<Integer> lj : dp[i - candidate]) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(candidate);
                    tmp.addAll(lj);
                    dp[i].add(tmp);
                }
            }
        }
        return dp[target];
    }
}

性能