39.組合總和?

項目場景：

給你一個?無重復元素?的整數數組?candidates?和一個目標整數?target?，找出?candidates?中可以使數字和為目標數?target?的 所有?不同組合?，并以列表形式返回。你可以按?任意順序?返回這些組合。

candidates?中的?同一個?數字可以?無限制重復被選取?。如果至少一個數字的被選數量不同，則兩種組合是不同的。?

對于給定的輸入，保證和為?target?的不同組合數少于?150?個。

示例?1：

輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個候選， 7 = 7 。
僅有這兩種組合。

示例?2：

輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

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

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates?的所有元素?互不相同
• 1 <= target <= 40

---

問題描述

? ? ? ? 本題可以利用遞歸，先將candidate數組排序，遞歸過程中，如果剩下的數字left為0則添加此時的路徑，如果此時i已經為candidate數組最后一個元素或者剩下的數字left小于此時的candidate數組元素，則回退return。遞歸過程中先不斷遞歸使得candidate最大，如果符合則將此時對應candidate數組的元素加入到path中，繼續(xù)遞歸left，否則就pop掉此時的元素，繼續(xù)進行遍歷。

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:       candidates.sort()ans=[]path=[]def dfs(i:int,left:int)->None:if left==0:ans.append(path.copy())returnif i==len(candidates) or left<candidates[i]:return dfs(i+1,left)path.append(candidates[i])dfs(i,left-candidates[i])path.pop()dfs(0,target)return ans

? ? ? ? 本題提交情況。

?

????????以上為本篇文章的全部內容，感謝你抽出寶貴的時間閱讀這篇文章。如果你有任何疑問或建議，歡迎在評論區(qū)留言，我們一起交流進步。愿你的代碼之路越走越順，生活充滿陽光！??