LeetCode 216. 组合总和 III

约 6 分钟
文章信息 8 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 LeetCode 75 腾讯 字节
标签
数组 回溯

题目描述

✅ 216. 组合总和 III

image-20260928223824247

image-20260928223824248

题意分析

从整数 1 到 9 中选择恰好 k 个不同数字，使它们的和等于目标 n，返回全部组合。每个数字最多使用一次，数字顺序不同但集合相同，仍算同一个组合。

两个条件必须同时满足：数量正好是 k，总和正好是 n。只达到目标和但没有选够，或选满数量后还有剩余目标，都不能收集。

解法：递增回溯剪枝

核心思路

[!blue]

将每条选择路径保持严格递增。选了当前数字后，下一层只尝试更大的数字，这既防止重复使用同一数字，也让每个无序组合只有一种递增表示，不需要在结果中再次去重。

递归状态 start 表示接下来最小可选值，need 表示还要选多少个数，remain 表示这些数需要凑出的和。need == 0 时结束，只在 remain == 0 时保存路径副本。

剩余数量还能提供和的界限。最小可能选择是从 start 开始的连续 need 个数，其和为 (2 * start + need - 1) * need / 2；最大可能选择是最大的 need 个数，其和为 (19 - need) * need / 2。剩余目标小于最小和或大于最大和，任何后续选择都不可能成功，可以整段剪去。

枚举当前值时，最大只需到 10 - need：选中它之后，右侧至少还要留出 need - 1 个不同数字。若当前值已经大于剩余目标，后面的候选只会更大，且所有数为正，可以直接结束本层循环。

做一次选择后减少数量和目标，递归回来再删除路径末尾，恢复兄弟分支的公共前缀。收集时复制路径，避免后续撤销改动已有答案。

解题步骤

  1. 从最小候选 1、剩余数量 k、剩余目标 n 和空路径开始。
  2. 数量已选满时检查剩余目标，满足则收集副本，无论是否满足都返回。
  3. 计算剩余数量能够形成的最小和、最大和，目标不在范围内就剪枝。
  4. 从 start 枚举到 10 - need，候选已经大于 remain 时停止循环。
  5. 追加候选，递归到 num + 1、need - 1、remain - num；返回后撤销末尾元素。
  6. 全部分支处理完，返回收集到的组合。

代码实现

class Solution {
    // 状态只需要记录当前可选起点、还需要选择几个数、剩余目标和，以及当前路径。
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();

        backtrack(1, k, n, new ArrayList<>(), res);

        return res;
    }

    private void backtrack(
            int start, int need, int remain, List<Integer> path, List<List<Integer>> res) {
        if (need == 0) {
            if (remain == 0) {
                // 复制当前方案，避免后续回溯修改已经收集的结果
                res.add(new ArrayList<>(path));
            }

            return;
        }

        // 用剩余数量的最小与最大可能和剪掉不可能分支
        int minSum = (start + start + need - 1) * need / 2;
        int maxSum = (19 - need) * need / 2;

        if (remain < minSum || remain > maxSum) {
            return;
        }

        // 当前选择至多到十减剩余数量，为后续保留足够不同数字
        for (int num = start; num <= 10 - need; num++) {
            if (num > remain) {
                break;
            }

            path.add(num);
            backtrack(num + 1, need - 1, remain - num, path, res);
            path.remove(path.size() - 1);
        }
    }
}

func combinationSum3(k int, n int) [][]int {
    // 状态只需要记录当前可选起点、还需要选择几个数、剩余目标和，以及当前路径。
    res := make([][]int, 0)
    path := make([]int, 0, k)

    var dfs func(start, need, remain int)
    dfs = func(start, need, remain int) {
        if need == 0 {
            if remain == 0 {
                pathCopy := make([]int, len(path))
                // 复制当前方案，避免后续回溯修改已经收集的结果
                copy(pathCopy, path)
                res = append(res, pathCopy)
            }
            return
        }
        // 用剩余数量的最小与最大可能和剪掉不可能分支
        minSum := (start + start + need - 1) * need / 2
        maxSum := (19 - need) * need / 2
        if remain < minSum || remain > maxSum {
            return
        }

        // 当前选择至多到十减剩余数量，为后续保留足够不同数字
        for num := start; num <= 10-need; num++ {
            if num > remain {
                break
            }
            path = append(path, num)
            dfs(num+1, need-1, remain-num)
            path = path[:len(path)-1]
        }
    }

    dfs(1, k, n)
    return res
}

复杂度分析

  • 时间复杂度：上界为 $O(k\binom{9}{k})$。递增且预留足够数量的搜索只沿可扩展为 k 元组合的前缀展开，每条完整组合对应至多 k 层；结果复制也需要 k 次操作。和的剪枝减少实际访问。
  • 空间复杂度：辅助空间为 $O(k)$，路径和递归深度至多为 k；返回结果另外需要与方案总长度对应的空间。

关键点总结

[!green]

  • 用严格递增的路径表示组合，同时去掉元素重复和排列重复。
  • 数量与和是独立的成功条件，递归状态分别保存。
  • 用最小/最大可达和判断整段无解，用当前值上界预留后续名额。
  • 追加与撤销保持对称，收集独立副本后才能安全继续搜索。

易错点总结

[!yellow]

  • 下一层仍从当前数字开始，会再次选择同一个数字；必须从 num + 1 开始。
  • 剩余和为零就立即收集，没有检查数量是否恰好用完。
  • 选满数量后仍继续递归，会产生超出 k 个数字的路径。
  • 最大当前值没有为剩余数量留位置，会探索大量不可能选满的分支。
  • 最小和公式没有随 start 更新，可能错误排除或放过当前区间的选择。
  • 直接保存可变路径对象或切片，后续回溯会改变先前结果，应复制路径内容。

相似题目

题目 难度 关联与区别
77. 组合 中等 同样固定选k个元素，本题还限制可选值为1到9并要求目标和。
39. 组合总和 中等 同样搜索目标和，原题允许候选重复使用，本题每个数最多一次且数量固定。
40. 组合总和 II 中等 在选择和撤销之间枚举组合；本题固定元素数量且只取一到九，该题候选只能用一次且需去重。
78. 子集 中等 在选择和撤销之间枚举组合；本题固定元素数量且只取一到九，该题输出所有选择长度的子集。
90. 子集 II 中等 在选择和撤销之间枚举组合；本题固定元素数量且只取一到九，该题排序后跳过同层重复值。
377. 组合总和 Ⅳ 中等 组合总和系列。III 从 1 到 9 中选定数量且不重复；IV 从给定集合重复取数并统计有序方案。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/88462841
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！