給定一個整數陣列
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
TIP
核心思路：Combination Sum I + Subsets II 的結合 — 每個元素只用一次，且需要去除重複組合。
- 與 Combination Sum I 的差異：每個元素只能用一次 → 遞迴從 i+1 開始
- 與 Subsets 的差異：有重複元素 → 排序 + 同層跳過
- 兩個技巧合在一起：排序 + backtrack(i+1) + 同層跳過
Approaches
1. Backtracking + HashSet Dedup — O(2^n) / O(n * 2^n)
- Idea: 用 HashSet 存儲組合結果，避免重複
- Time:
O(2^n) - Space:
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 + Skip Same Level — O(2^n) / O(n)
- Idea: 排序後，同層跳過重複元素，每個元素只用一次（遞迴 i+1），加上排序剪枝
- Time:
O(2^n) - Space:
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 的綜合應用
- Key trick: 掌握三個控制參數的差異 —
backtrack(i)可重複選、backtrack(i+1)不可重複選、i > start判斷同層跳過