Python组合总和怎么实现

发布时间:2021-11-26 09:21:28 作者:iii
来源:亿速云 阅读:150

本篇内容主要讲解“Python组合总和怎么实现”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Python组合总和怎么实现”吧!

题目


给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明:

示例 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]
]

提示:

解题思路


思路:回溯

先审题,题目给定无重复元素数组和目标值 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组合总和怎么实现”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

推荐阅读:
  1. Python numpy如何实现数组合并
  2. Python怎么实现两个列表的最小索引总和

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

python

上一篇:如何进行mqtt协议中broker的moqutte源码分析

下一篇:C#如何实现基于Socket套接字的网络通信封装

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》