LeetCode 組合生成：遞歸回溯求所有 k 組合

題目描述

給定整數 n 和 k，返回 1...n 中所有可能的 k 個數的組合。

遞歸回溯

從 1 開始嘗試選擇或不選擇當前數字。若已選 k 個，加入結果。若剩餘數字不足以湊齊 k 個，剪枝返回。

代碼實現 (Python)

class Solution:
    def combine(self, n, k):
        res = []
        def backtrack(start, path):
            if len(path) == k:
                res.append(path[:])
                return
            for i in range(start, n+1):
                path.append(i)
                backtrack(i+1, path)
                path.pop()
        backtrack(1, [])
        return res

複雜度

• 時間：O(C(n,k) * k)
• 空間：O(k) 遞歸棧 + 結果空間