组合总和

木又AI帮

发布于 2020-07-07 12:05:03

5160

发布于 2020-07-07 12:05:03

题目：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

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-07-03，如有侵权请联系 cloudcommunity@tencent.com 删除

dfs