题目0039:组合总和

题目描述

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

解题技巧

思路:根据示例1输入: candidates = [2,3,6,7],target = 7。

候选数组里有2,如果找到了7-2=5的所有组合,再在之前加上2,就是7的所有组合;同理考虑3,如果找到了7-3=4的所有组合,再在之前加上3,就是7的所有组合,依次这样找下去;上面的思路就可以画成下面的树形图。 其实这里思路已经介绍完了，大家可以自己尝试在纸上画一下这棵树。然后编码实现，如果遇到问题，再看下面的文字。

如果这样编码的话,会发现提交不能通过,这是因为递归树画的有问题,下面看一下是什么原因。

画出图以后,我看了一下,我这张图画出的结果有4个0,对应的路径是[[2, 2, 3],[2, 3, 2], [3, 2, 2], [7]],而示例中的解集只有[[7], [2, 2, 3]],很显然,重复的原因是在较深层的结点值考虑了之前考虑过的元素,因此我们需要设置“下一轮搜索的起点”即可(这里可能没有说清楚,已经尽力了)。

去重复

在搜索的时候,需要设置搜索起点的下标begin,由于一个数可以使用多次,下一层的结点从这个搜索起点开始搜索; 在搜索起点begin之前的数因为以前的分支搜索过了,所以一定会产生重复。

• 剪枝提速

如果一个数位搜索起点都不能搜索到结果,那么比它还大的数肯定搜索不到结果,基于这个想法,我们可以对输入数组进行排序,以减少搜索的分支;

排序是为了提高搜索速度,非必要;

搜索问题一般复杂度较高,能剪枝就尽量需要剪枝。把候选数组排个序,遇到一个较大的数,如果以这个数为起点都搜索不到结果,后面的数就更搜索不到结果了。

from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        size = len(candidates)
        if size == 0:
            return []

        # 剪枝是为了提速，在本题非必需
        candidates.sort()
        # 在遍历的过程中记录路径，它是一个栈
        path = []
        res = []
        # 注意要传入 size ，在 range 中， size 取不到
        self.__dfs(candidates, 0, size, path, res, target)
        return res

    def __dfs(self, candidates, begin, size, path, res, target):
        # 先写递归终止的情况
        if target == 0:
            # Python 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
            # 或者使用 path.copy()
            res.append(path[:])
            return

        for index in range(begin, size):
            residue = target - candidates[index]
            # “剪枝”操作，不必递归到下一层，并且后面的分支也不必执行
            if residue < 0:
                break
            path.append(candidates[index])
            # 因为下一层不能比上一层还小，起始索引还从 index 开始
            self.__dfs(candidates, index, size, path, res, residue)
            path.pop()


if __name__ == '__main__':
    candidates = [2, 3, 6, 7]
    target = 7
    solution = Solution()
    result = solution.combinationSum(candidates, target)
    print(result)