題目出處
難度
medium
個人範例程式碼
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates:
return []
ans = []
self.dfs(sorted(candidates), target, 0, [], ans)
return ans
def dfs(self, candidates, target, start_idx, combination, ans):
# end of recursion
if target < 0:
return
if target == 0:
ans.append(list(combination)) # deepcopy
return
# define
for idx in range(start_idx, len(candidates)):
if idx != start_idx and candidates[idx] == candidates[idx-1]: # remove duplicate
continue
combination.append(candidates[idx])
self.dfs(candidates, target-candidates[idx], idx+1, combination, ans) # no duplicate use
combination.pop()
算法說明
本題是 Combinations 系列的第 3 題，前面的題目可以參考：
第 1 題：不允許重複，給定數字範圍的全部組合，目標是指定組合內固定的數量。
第 2 題：允許重複，順序不同視為相同結果，也就是說「(1,2,3) 與 (3, 2, 1) 是一個結果」
第 3 題：允許有限重複(題目指定上限數量)，求全部組合。
第 4 題：不允許重複，給定數字範圍的全部組合，目標是求指定的和。
第 5 題：允許重複，但順序不同視為不同結果，也就是說「(1,2,3) 與 (3, 2, 1) 是兩個結果」。(這題已經可以當作排列的題目了。)
組合類的問題，使用 dfs 搜尋出全部的組合，在判斷可行的方案。
與允許使用重複的前一題比較，這題要多處理「數組內建重複」的部分，
因此我們多使用了
「idx != start_idx」：當 idx 不等於「起始位置」
這個判斷條件非常重要，
我們只判斷起始位置，因為有可能會有 [1,1,6] 這種 case 要處理
我們讓頭兩組 [1, 1] 能夠被計算為一個結果，是第一組也被我們控制在唯一的一組。
如果數組有 [1, 1, 1]， 我們在搜尋前兩個 [1, 1] 就會決定了這唯一的結果。
「candidates[idx] candidates[idx-1]」
判斷重複的時候，用 continue 直接略過。
(for 搭配 continue，比起直接用 while 略過，感覺程式可讀性會更好。)
最近在練習程式碼本身就可以自解釋的 Coding style，可以嘗試直接閱讀程式碼理解
input handling
如果沒有 candidates，直接 return []
Boundary conditions
見上述說明