组合总和
力扣第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]
]
回溯思想
当我第一眼看到这个题的时候,我第一时间想到就是DP,但是仔细阅读题目的时候就可以发现,这道题是求所有可能的总和,而动态规划只能解决最有问题,所以以后遇到求总和问题的时候,就应该先想到回溯的思想去解决问题.
回溯的处理思想,有点类似枚举搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。
相信看过明日边缘和蝴蝶效应这些电影的人应该很容易去理解回溯,下面就来用回溯思想去分析一下这道题.
可以看到,以蓝色点递归可以找到所有的组合
但是有一些节点是重复的,因为递归时没有加限制条件,更深一层的递归又会重复去考虑之前已经计算过的组合,所以需要去排序.
排好序之后,当候选数组的元素比目标数还大时,该元素后面的数可以都不用去考虑了.
1 | class Solution: |
复杂度分析
时间复杂度:每一次递归遍历考虑所有可能的组合,所以时间复杂度为$$O(n^2)$$
空间复杂度:O(n)
总结
回溯思想可能是一个时间复杂度较高的算法,很多时候可以用dp去优化,但是在枚举所有可能的结果的时候,就是发挥它的特点的时候了,不要因为复杂度高就不去考虑,所以还是的脚踏实地去学习编程吧!!!
相似题目