題目鏈接

難度：中等 ??????類型： 深度優先搜索

給定一個數組 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中只能使用一次。

示例1

所求解集為:

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

示例2

輸入: candidates = [2,5,2,1,2], target = 5,

所求解集為:

[

[1,2,2],

[5]

]

解題思路

“解集不能包含重復的組合”，那就排個序，相鄰兩數相同， 到第二個就跳過，做到結果的同一位上同樣大小的數只使用一個，

剩下的和39.組合總和一致

代碼實現

class Solution(object):

def combinationSum2(self, candidates, target):

"""

:type candidates: List[int]

:type target: int

:rtype: List[List[int]]

"""

c = sorted(candidates)

res = []

len_c = len(c)

def dfs(target, index, path):

if target == 0:

res.append(path)

return

for i in range(index, len_c):

if i>index and c[i] == c[i-1]:

continue

if c[i]>target:

break

dfs(target-c[i], i+1, path+[c[i]])

dfs(target, 0, [])

return res

總結

以上是生活随笔為你收集整理的python两两组合求和_LeetCode-python 40.组合总和 II的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。