萌新练习写代码的每日一练：组合总和

给定一个无重复元素的数组 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]
]

思路：老套路了，看到“所有组合”，就要思考递归方法（话说最近做题老是递归法解的23333），一开始我的思路是一层一层加，比如说示例1吧，第一层是2，第二层是4,5,8,9，但这么做会漏掉本来就符合条件的7，还需要加各种判断条件，而且加到最后的处理也比较麻烦。果断不钻死胡同了，逆向思维之减法，把target作为根去做，直接解释过于麻烦，上图！

萌新练习写代码的每日一练：组合总和

再往下画就太乱了，不过画到这里应该能解释清楚了，第一次让target减去数组里的所有值，然后记录当前target值，=0的就符合，加入空数组res中，<0的直接淘汰，>0的存储到临时数组path中继续递归。

代码：

from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        res = []
        length = len(candidates)
        path = []
        if candidates == "":
            return res

        def dfs(candidates, begin, length, path, res, target):
            if target < 0:
                return 0
            if target == 0:
                res.append(path)
                return 0
            for i in range(begin, length):
                dfs(candidates, i, length, path + [candidates[i]], res, target - candidates[i])
        dfs(candidates, 0, length, path, res, target)
        return res

题目来自LeetCode第39题

萌新练习写代码的每日一练：组合总和

相关推荐