40. Combination Sum II

Question: Combination Sum II

Solution

可以先參考 39. Combination Sum 與 90. Subsets II

同樣是：放與不放去思考

但因為 candidates 中有重複的 elements，所以放與不放變成：

• 如果放 1，則代表這邊的結果是：至少包含一個 1
• 不放 1 的那一邊，則是：完全沒有 1

class Solution:

def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:

res = list()

candidates.sort()

print(candidates)

subset = list()

def dfs(i, residule):

if residule == 0:

res.append(subset.copy())

return

elif residule < 0 or i > len(candidates) - 1:

return

else:

subset.append(candidates[i])

dfs(i + 1, residule - candidates[i])

subset.pop()

while i < len(candidates) - 1 and candidates[i] == candidates[i + 1]:

i += 1

dfs(i + 1, residule)

dfs(0, target)

return res

Video Solution