1 題目

給定一個候選人編號的集合 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中只能使用 一次 。

注意：解集不能包含重復的組合。

示例 1:

輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

輸入: candidates = [2,5,2,1,2], target = 5,
輸出:
[
[1,2,2],
[5]
]

2 解析

我們主要需要解決的就是數組元素存在重復情況的問題，下面是解決的辦法：

首先先將數組進行排序，這樣重復的元素位置相鄰，可以快速去重；
因為不允許組合重復（相同數字不同排序視為重復），所以遞歸每層不能存在重復的元素。
為了避免重復選擇同個元素，進入下層遞歸時，選擇下一個索引位置對應的元素。
這裡用一個簡單圖示來加深理解，如下：

3 Python實現

class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# 將數組進行升序排序
candidates.sort()
# 結果列表
ans = []
# 可能組合
tmp = []
def back_dfs(idx, total):
if total == target:
ans.append(tmp[::])
return
if total > target:
return
for i in range(idx, len(candidates)):
# 這裡限制同一層不能選擇值相同的元素
# 若有相同的元素，優先選擇索引靠前的
if candidates[i-1] == candidates[i] and i-1 >= idx:
continue
total += candidates[i]
tmp.append(candidates[i])
# 這裡注意，與 39 題不同，進入遞歸下一層
# 從當前索引的下一位開始選取，避免重復選取同個元素
back_dfs(i+1, total)
# 回溯
tmp.pop()
total -= candidates[i]
total = 0
back_dfs(0, total)
return ans