40. Combination Sum II

Medium

Description

給定一個整數陣列 candidates（可能有重複）和目標值 target，找出所有 candidates 中數字之和等於 target 的唯一組合。每個數字只能使用一次。

Example:

Input: candidates = [10,1,2,7,6,1,5], target = 8 Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

Intuition#

核心思路：Combination Sum I + Subsets II 的結合 — 每個元素只用一次，且需要去除重複組合。

與 Combination Sum I 的差異：每個元素只能用一次 → 遞迴從 i+1 開始
與 Subsets 的差異：有重複元素 → 排序 + 同層跳過
兩個技巧合在一起：排序 + backtrack(i+1) + 同層跳過

Approaches#

1: Backtracking + HashSet 去重#

概念: 用 HashSet 存儲組合結果，避免重複
時間複雜度: O(2^n)
空間複雜度: O(n * 2^n)

class Solution {
    fun combinationSum2(candidates: IntArray, target: Int): List<List<Int>> {
        candidates.sort()
        val result = HashSet<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 + 1, remain - candidates[i])
                current.removeAt(current.lastIndex)
            }
        }

        backtrack(0, target)
        return result.toList()
    }
}

⭐2: Backtracking + 同層跳過#

概念: 排序後，同層跳過重複元素，每個元素只用一次（遞迴 i+1），加上排序剪枝
時間複雜度: O(2^n)
空間複雜度: O(n) - 遞迴深度

class Solution {
    fun combinationSum2(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
                if (i > start && candidates[i] == candidates[i - 1]) continue  // 同層跳過
                current.add(candidates[i])
                backtrack(i + 1, remain - candidates[i])
                current.removeAt(current.lastIndex)
            }
        }

        backtrack(0, target)
        return result
    }
}

🔑 Takeaways#

Pattern: 組合去重 = 排序 + 同層跳過，是 Combination Sum 和 Subsets II 的綜合應用
關鍵技巧: 掌握三個控制參數的差異 — backtrack(i) 可重複選、backtrack(i+1) 不可重複選、i > start 判斷同層跳過