回溯中等1 种解法

#216组合总和 III

从 1 到 9 中选择 k 个互不相同的数，使其和等于 n。

#回溯#组合#剪枝

解题主线

下一层从 i + 1 开始，同时满足不重复和组合不计顺序。

利用剩余槽位可达到的最小和、最大和，可以在进入循环前排除不可能分支。

解法 1：定长组合 + 和界剪枝

传递剩余目标和，根据剩余槽位和 start 计算理论最小和与最大和，再枚举当前值。

时间复杂度

O(k × C(9,k))，9 为固定候选范围

空间复杂度

O(k)，不计输出

216. 组合总和 III · 定长组合 + 和界剪枝

java

import java.util.ArrayList;
import java.util.List;

final class Solution {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(k, n, 1, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int k, int remaining, int start,
                           List<Integer> path, List<List<Integer>> result) {
        int slots = k - path.size();
        if (slots == 0) {
            if (remaining == 0) {
                result.add(new ArrayList<>(path));
            }
            return;
        }
        if (start + slots - 1 > 9) {
            return;
        }
        int minimum = slots * (2 * start + slots - 1) / 2;
        int maximum = slots * (19 - slots) / 2;
        if (remaining < minimum || remaining > maximum) {
            return;
        }

        for (int value = start; value <= 9; value++) {
            if (value > remaining) {
                break;
            }
            path.add(value);
            backtrack(k, remaining - value, value + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

传递剩余目标和，根据剩余槽位和 start 计算理论最小和与最大和，再枚举当前值。

边界与易错点

路径达到 k 时，无论剩余和是否为 0 都应结束当前分支。
用可变 sum 时做选择与撤销必须严格对称；改传 remaining 可减少共享状态错误。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q216_combinationSum3.java