題目在此 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
|
😎
相關文章