您好,登录后才能下订单哦!
本篇内容主要讲解“Python组合总和怎么实现”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Python组合总和怎么实现”吧!
给定一个无重复元素的数组 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
先审题,题目给定无重复元素数组和目标值 target,要求找出数组中所有可以使数组元素和为 target 的组合。
其中数组中的元素都为正整数,可以重复使用数组中的元素,但是解集中不能存在重复的组合。
这里可以看示例 1:
输入:candidates = [2,3,6,7], target = 7, 所求解集为: [ [7], [2,2,3] ]
这里答案并没有 [2,3,2] 或 [3,2,2],因为这两者就被视为与 [2,2,3] 为重复的组合,这里需要特别注意。
在这里 $\color{red}{✖}$ 表示不选择此元素,这样就可以避免元素组合重复的情况,$\color{green}{✖}$ 表示当前路径选择元素和大于目标值 target,而 $\color{green}{✔}$ 则表示当前路径选择元素和等于目标值,可以将此组合添加到返回列表中。
在上面的图例中,只是简单画出了一个分支的情况,但是其他分支选择的策略相同,这里就省略了。若有不太明白的地方,建议可以自行在草稿上进行补全,也帮助自己理解。
那么就按照上面图例中的思路,用代码进行实现,具体如下。
class Solution: def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: # 结果列表 ans = [] # 可能的组合 tmp = [] def helper(idx, total): """回溯,求组合总和 Args: idx: 选取元素索引 total: 组合中的元素和 """ # 基准条件 # 当元素和大于目标值,直接返回 if total > target: return # 当元素和等于目标值,将组合添加到结果中,返回 if total == target: ans.append(tmp[::]) return # 进入分支,同时避免重复组合 for i in range(idx, len(candidates)): # 更新 total 值, total += candidates[i] # 同时将当前元素尝试添加到组合中 tmp.append(candidates[i]) # 再次进入递归 # 这里可以看文章图例,递归向下,可选元素是从自身开始选择 # 这里同时也能避免组合重复,因为不会再次选择索引 i 前面对应的元素 helper(i, total) # 回溯,回退组合元素及 total 值 tmp.pop() total -= candidates[i] total = 0 helper(0, total) return ans
到此,相信大家对“Python组合总和怎么实现”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。