回溯中等1 种解法

#77组合

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

#回溯#组合#剪枝

原题

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

1 <= n <= 20
1 <= k <= n

查看原题

解题主线

组合只关心选择集合而不关心顺序，因此下一层从 i + 1 开始。
当剩余可选数字不足以填满路径时无需继续循环，可收紧循环上界。

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

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

时间复杂度： O(k × C(n,k))，复制每个组合需要 O(k)
空间复杂度： O(k)，不计输出

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();
        // 收紧上界：剩余候选不足 remaining 个时直接剪枝。
        for (int value = start; value <= n - remaining + 1; value++) {
            path.add(value);
            // 下一层只选更大的数，避免重复组合。
            backtrack(n, k, value + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

边界与易错点

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

整理来源

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

backtrack/Q077_combine.java