组合

🟡 Medium · 🏷️ 数组、回溯 · LeetCode#77

📖 题目

给定 n 和 k，返回 [1, n] 里所有 k 个数的组合。

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

💡 思路

组合本质是固定长度的子集——同样用 start 只往后选（避免 [1,2] 和 [2,1] 被算成两个），区别是子集每个节点都记录，这题只记录长度正好等于 k 的节点。

跟子集代码几乎一样，唯一区别是记录条件从"每个节点"变成"len(path) == k"。

💻 代码

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []

        def backtrack(start: int, path: List[int]):
            if len(path) == k:
                result.append(path[:])
                return
            for a in range(start, n + 1):
                path.append(a)
                backtrack(a + 1, path)
                path.pop()

        backtrack(1, [])
        return result

时间复杂度 O(C(n,k) × k)，C(n,k) 个组合，每个要复制 k 个元素；空间复杂度 O(k)。如果 n 很大，还可以剪枝——剩下的数已经不够凑满 k 个时提前放弃：range(start, n - (k - len(path)) + 2)，但这题规模通常很小，不剪枝也够快。

🔀 回溯三兄弟

	子集	排列	组合（这题）
能不能回头选	不能（start）	能（not in path）	不能（start）
记录时机	每个节点	只在叶子	长度等于 k 时

组合就是子集的"能不能回头"加上排列的"到了特定深度才记录"，理解这两个维度，回溯题基本都能套上去。