回溯中等1 种解法

#77组合

从 1 到 n 中选择 k 个不同整数，返回所有组合。

#回溯#组合#剪枝

解题主线

组合只关心选择集合而不关心顺序，因此下一层从 i + 1 开始。

当剩余可选数字不足以填满路径时无需继续循环，可收紧循环上界。

解法 1：带剩余数量剪枝的回溯

路径达到 k 时记录结果；根据还需要的元素数计算本层起点可到达的最大值。

时间复杂度

O(k × C(n,k))，复制每个组合需要 O(k)

空间复杂度

O(k)，不计输出

77. 组合 · 带剩余数量剪枝的回溯

java

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

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

    private void backtrack(int n, int k, int start,
                           List<Integer> path, List<List<Integer>> result) {
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        int remaining = k - path.size();
        for (int value = start; value <= n - remaining + 1; value++) {
            path.add(value);
            backtrack(n, k, value + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

路径达到 k 时记录结果；根据还需要的元素数计算本层起点可到达的最大值。

边界与易错点

循环上界应为 n - remaining + 1，少加或多加 1 都会漏解或产生无效分支。
达到 k 个元素后要立即返回，避免继续扩展。

整理来源

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

backtrack/Q077_combine.java