网站建设做什么会计分录,响应式网站做法,上海域名网站吗,谷歌关键词39.组合总和
项目场景#xff1a;
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target #xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 #xff0c;并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同…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 302 candidates[i] 40candidates 的所有元素 互不相同1 target 40 问题描述 本题可以利用递归先将candidate数组排序递归过程中如果剩下的数字left为0则添加此时的路径如果此时i已经为candidate数组最后一个元素或者剩下的数字left小于此时的candidate数组元素则回退return。递归过程中先不断递归使得candidate最大如果符合则将此时对应candidate数组的元素加入到path中继续递归left否则就pop掉此时的元素继续进行遍历。
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 left0:ans.append(path.copy())returnif ilen(candidates) or leftcandidates[i]:return dfs(i1,left)path.append(candidates[i])dfs(i,left-candidates[i])path.pop()dfs(0,target)return ans 本题提交情况。 以上为本篇文章的全部内容感谢你抽出宝贵的时间阅读这篇文章。如果你有任何疑问或建议欢迎在评论区留言我们一起交流进步。愿你的代码之路越走越顺生活充满阳光
