39. Combination Sum

Medium

Description

給定一個不重複的正整數陣列 candidates 和目標值 target，找出所有 candidates 中數字之和等於 target 的唯一組合。同一個數字可以被無限次選取。

Example:

Input: candidates = [2,3,6,7], target = 7 Output: [[2,2,3],[7]]

Intuition#

核心思路：回溯搜尋所有組合，同一數字可重複選取（遞迴不移到下一個 index），target 減到 0 就是一組解。

和子集問題類似，但每個元素可以重複選取
遞迴時不移到 i + 1 而是留在 i，允許重複選擇同一個數
剪枝：當 remain < 0 時直接返回；先排序可以更早剪枝

Approaches#

1: Backtracking（無排序）#

概念: 對每個 candidate，選擇加入（stay at i）或跳過（move to i+1），直到 remain 為 0 或負數
時間複雜度: O(n^(t/m)) - t 為 target，m 為最小 candidate
空間複雜度: O(t/m) - 遞迴深度

class Solution {
    fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
        val result = mutableListOf<List<Int>>()
        val current = mutableListOf<Int>()

        fun backtrack(start: Int, remain: Int) {
            if (remain == 0) {
                result.add(ArrayList(current))
                return
            }
            if (remain < 0) return

            for (i in start until candidates.size) {
                current.add(candidates[i])
                backtrack(i, remain - candidates[i])  // 不是 i+1，因為可重複選
                current.removeAt(current.lastIndex)
            }
        }

        backtrack(0, target)
        return result
    }
}

⭐2: Backtracking + 排序剪枝#

概念: 先排序 candidates，當 candidates[i] > remain 時，後面更大的數也不用看了，直接 break
時間複雜度: O(n^(t/m)) - 但剪枝大幅減少實際搜尋量
空間複雜度: O(t/m)

class Solution {
    fun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {
        candidates.sort()
        val result = mutableListOf<List<Int>>()
        val current = mutableListOf<Int>()

        fun backtrack(start: Int, remain: Int) {
            if (remain == 0) {
                result.add(ArrayList(current))
                return
            }

            for (i in start until candidates.size) {
                if (candidates[i] > remain) break  // 剪枝
                current.add(candidates[i])
                backtrack(i, remain - candidates[i])
                current.removeAt(current.lastIndex)
            }
        }

        backtrack(0, target)
        return result
    }
}

🔑 Takeaways#

Pattern: 組合問題回溯模板，「可重複選取」只需遞迴時不移動 index
關鍵技巧: 排序 + 剪枝是回溯法效率提升的標準手段；backtrack(i, ...) vs backtrack(i+1, ...) 決定是否允許重複選取