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

candidates?中的數字可以無限制重復被選取。

說明：

• 所有數字（包括?target）都是正整數。
• 解集不能包含重復的組合。?

示例?1：

輸入：candidates = [2,3,6,7], target = 7 所求解集為：[[7],[2,2,3] ]

示例?2：

輸入：candidates = [2,3,5], target = 8 所求解集為： [[2,2,2,2],[2,3,3],[3,5] ]

?

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每個元素都是獨一無二的。
• 1 <= target <= 500

遞歸

首先把candidates排序，然后每次取一個數放進ans，將剩下的余數繼續遞歸搜索。

Code

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:def find(start, use, remain):for index, value in enumerate(candidates[start:]):if value == remain:ans.append(use + [value])elif value < remain:find(start + index, use + [value], remain - value)else:returnans = []candidates.sort()find(0, [], target)return ans

總結

以上是生活随笔為你收集整理的39. Combination Sum 组合总和的全部內容，希望文章能夠幫你解決所遇到的問題。

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