组合总和

题目:39. 组合总和

链接:https://leetcode-cn.com/problems/combination-sum

给定一个无重复元素的数组 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、DFS典型应用。

代码:

class Solution(object):
    def __init__(self):
        self.res = []
        self.ls = []

    def dfs(self, start, target, current):
        if target == 0:
            self.res.append(current)
            return 
        for i in range(start, len(self.ls)):
            c = self.ls[i]
            if c > target:
                break
            current2 = copy.copy(current)
            current2.append(c)
            self.dfs(i, target - c, current2)


    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        candidates.sort()
        self.ls = candidates
        for i, c in enumerate(candidates):
            if c > target:
                break
            self.dfs(i, target - c, [c])
        return self.res

本文分享自微信公众号 - 木又AI帮(gh_eaa31cab4b91),作者:木又

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-07-03

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 组合总和 II

    链接:https://leetcode-cn.com/problems/combination-sum-ii

    木又AI帮
  • 打卡群刷题总结0826——组合总和

    链接:https://leetcode-cn.com/problems/combination-sum

    木又AI帮
  • 打卡群刷题总结0723——组合

    链接:https://leetcode-cn.com/problems/combinations

    木又AI帮
  • 组合总和 II

    链接:https://leetcode-cn.com/problems/combination-sum-ii

    木又AI帮
  • 打卡群刷题总结0826——组合总和

    链接:https://leetcode-cn.com/problems/combination-sum

    木又AI帮
  • [leetcode]39. Combin

    意思说 给你一组正数C,然后 给你一个目标数T, 让你从那组C中找到加在一起等于T的那些组合。 比如 给你7 然后 从[2,3,6,7]中可以找到[2,2,...

    py3study
  • iOS - 实现UINavigation全屏滑动返回(二)

    LinXunFeng
  • 工程管理篇 | 多Targets

    很多时候,工程管理是一个很实际的技能,我们在实际开发中普遍有很多环境:测试环境、开发环境、生产环境等。还有可能遇到需要创建两个很多内容相同,部分功能不同的工程。

    進无尽
  • ios 扩大UIButton点击范围

    先了解Hit-Test请看上一篇文章 https://www.jianshu.com/writer#/notebooks/4989829/notes/3314...

    赵哥窟
  • K-SVD字典学习及其实现(Python)

    算法求解思路为交替迭代的进行稀疏编码和字典更新两个步骤. K-SVD在构建字典步骤中,K-SVD不仅仅将原子依次更新,对于原子对应的稀疏矩阵中行向量也依次进行了...

    卡尔曼和玻尔兹曼谁曼

扫码关注云+社区

领取腾讯云代金券