給定兩個整數
n和k，回傳從1到n中選k個數的所有組合。可以任意順序回傳。
Example:
Input: n = 4, k = 2 Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Intuition
TIP
核心思路：回溯法從 start 開始向後選數，選滿 k 個時收集結果。
- 組合問題的經典模板：用 start 參數確保只往後選，避免重複
- 每層遞迴選一個數，當已選 k 個數時加入結果
- 可用剪枝優化：剩餘數不夠選時提前終止
Approaches
1. Basic Backtracking — O(C(n,k) * k) / O(k)
- Idea: 從 start 開始遍歷到 n，每次選一個數後遞迴，回溯時移除
- Time:
O(C(n,k) * k)- 共 C(n,k) 個組合，每個複製需 O(k) - Space:
O(k)- 遞迴深度
class Solution {
fun combine(n: Int, k: Int): List<List<Int>> {
val result = mutableListOf<List<Int>>()
val current = mutableListOf<Int>()
fun backtrack(start: Int) {
if (current.size == k) {
result.add(ArrayList(current))
return
}
for (i in start..n) {
current.add(i)
backtrack(i + 1)
current.removeAt(current.lastIndex)
}
}
backtrack(1)
return result
}
}⭐ 2. Backtracking + Pruning — O(C(n,k) * k) / O(k)
- Idea: 在基本回溯上加入剪枝：若剩餘可選數量不足以填滿組合，提前終止
- Time:
O(C(n,k) * k) - Space:
O(k)
class Solution {
fun combine(n: Int, k: Int): List<List<Int>> {
val result = mutableListOf<List<Int>>()
val current = mutableListOf<Int>()
fun backtrack(start: Int) {
if (current.size == k) {
result.add(ArrayList(current))
return
}
val need = k - current.size
// 剪枝：從 start 到 n 至少要有 need 個數
for (i in start..n - need + 1) {
current.add(i)
backtrack(i + 1)
current.removeAt(current.lastIndex)
}
}
backtrack(1)
return result
}
}🔑 Takeaways
- Pattern: 組合問題是回溯法三大基礎之一，用 start 參數往後選避免重複
- Key trick: 剪枝條件
i <= n - (k - current.size) + 1可以大幅減少搜索空間；此題是 39. Combination Sum 和 78. Subsets 的基礎