Re: [閒聊] 每日leetcode
40. Combination Sum II
## 思路
要列出組合就用backtracking
每個candidate只能用一次 但可能會有重複的num
所以必須要考慮重複的arr
e.g. [2,1,2,2] target: 5
[[1,2,2]] # 1+任取兩個2
-> 先做排序, 然後在backtracking的過程中skip掉重複的num
## Code
```python
class Solution:
def combinationSum2(self, candidates: List[int], target: int) ->
List[List[int]]:
candidates.sort()
n = len(candidates)
ans = []
arr = []
def backtrack(i, curr_sum):
if curr_sum == target:
ans.append(arr[:])
return
if i == n or curr_sum > target:
return
for j in range(i, n):
# skip duplicate
if j > i and candidates[j] == candidates[j-1]:
continue
if candidates[j] + curr_sum > target:
break
arr.append(candidates[j])
backtrack(j+1, curr_sum + candidates[j])
arr.pop()
backtrack(0, 0)
return ans
```
--
http://i.imgur.com/OLvBn3b.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 185.213.82.61 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723534606.A.605.html
討論串 (同標題文章)
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 704 之 1549 篇)：