題目描述:給定兩個整數 n 和 k,回傳從 1 到 n 中選出 k 個數字的所有組合(不計順序,不重複使用)。
解題思路:
這是組合問題的標準回溯解法。與排列不同,組合不考慮順序,因此每次遞迴只往後選(start 索引只增不減),避免重複生成。
關鍵設計:
start 參數:每次遞迴傳入當前可選的最小數字,確保組合元素嚴格遞增。current 到長度 k 時,直接返回。具體條件:當前可選的起點 start 最大為 n - (k - current.size()) + 1,超過此值必然湊不滿 k 個元素。此剪枝在 n 較大、k 較小時效果顯著,可大幅減少無效的遞迴分支。
時間複雜度:O(C(n,k) × k) — 共有 C(n,k) 個組合,每個組合需要 O(k) 時間複製到結果集,因此總時間複雜度為 O(C(n,k) × k)。
空間複雜度:O(k) — 遞迴深度最大為 k(每層選一個數字),current 陣列大小也為 k;不計輸出結果所佔的空間。
1. Initialize result=[], current=[]
2. Define backtrack(start):
a. If len(current) == k: append copy of current to result; return
b. need = k - len(current)
c. For i from start to (n - need + 1) inclusive:
- Append i to current
- Recurse backtrack(i + 1)
- Pop last element from current
3. Call backtrack(1); return result方法一:迭代法(Bit Manipulation)
枚舉 0 到 2^n - 1 的所有整數,對每個整數取其二進位表示中恰好有 k 個 1 的那些,對應的位元位置(+1)即構成一個組合。時間複雜度 O(2^n × n),在 n 較大時效率很差,但概念簡潔,適合理解組合的位元表示。
方法二:遞推公式法(Pascal's Triangle / Lexicographic Construction)
利用組合數的遞推性 C(n,k) = C(n-1,k-1) + C(n-1,k):從 C(1,1)={[1]} 出發,逐步構造更大的組合集,每次在已有組合後追加新數字或跳過。時間複雜度 O(C(n,k) × k),與回溯法相同,但程式碼以迭代實現,不用遞迴棧。適合在系統不支援深層遞迴時使用。
i <= n - need + 1 可以減少多少無效遞迴?當 k 接近 n/2 時剪枝效果最弱還是最強?1..n 改為任意給定的陣列(可能含重複),去重的組合問題(LC 40)需要在哪裡加入額外的跳過條件?