LeetCode 筆記 - 40. Combination Sum II

題目在此 40. Combination Sum II

給一個數列與目標數,請從數列找出相加的組合等於目標數,每個數字只能用一次

解題思維

如果沒解過第一題可以看這篇 LeetCode 筆記 - 39. Combination Sum

這題一樣是用 Depth First Search 跑一次就可以了

其中這裡有用到一個技巧來避開重複的組合

1
2
if i > last_index + 1 and candidates[i] == candidates[i- 1]:
continue

在這篇筆記有比較詳細的解釋 LeetCode 筆記 - 47. Permutations II

最後的小技巧就是先 Sorting,來跳過一些計算

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:

if sum(candidates) < target:
return []

candidates.sort()
candidate_size = len(candidates)

self.result = []
def dfs(last_index, result, count):
if count == target:
self.result.append(result)
return

for i in range(last_index + 1, candidate_size):
if count + candidates[i] > target:
break

if i > last_index + 1 and candidates[i] == candidates[i- 1]:
continue

dfs(i, result + [candidates[i]], count + candidates[i])

dfs(-1, [], 0)

return self.result

😎

也許你也會想看看