77. Combinations

Medium

Description

給定兩個整數 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#

核心思路：回溯法從 start 開始向後選數，選滿 k 個時收集結果。

組合問題的經典模板：用 start 參數確保只往後選，避免重複
每層遞迴選一個數，當已選 k 個數時加入結果
可用剪枝優化：剩餘數不夠選時提前終止

Approaches#

1: 基本回溯#

概念: 從 start 開始遍歷到 n，每次選一個數後遞迴，回溯時移除
時間複雜度: O(C(n,k) * k) - 共 C(n,k) 個組合，每個複製需 O(k)
空間複雜度: 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: 回溯 + 剪枝#

概念: 在基本回溯上加入剪枝：若剩餘可選數量不足以填滿組合，提前終止
時間複雜度: O(C(n,k) * k)
空間複雜度: 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 參數往後選避免重複
關鍵技巧: 剪枝條件 i <= n - (k - current.size) + 1 可以大幅減少搜索空間；此題是 39. Combination Sum 和 78. Subsets 的基礎