Jiang's blog

每日一道算法之--组合总和

Word count: 817Reading time: 3 min
2020/03/05 Share

组合总和

力扣第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,但是仔细阅读题目的时候就可以发现,这道题是求所有可能的总和,而动态规划只能解决最有问题,所以以后遇到求总和问题的时候,就应该先想到回溯的思想去解决问题.

回溯的处理思想,有点类似枚举搜索。我们枚举所有的解,找到满足期望的解。为了有规律地枚举所有可能的解,避免遗漏和重复,我们把问题求解的过程分为多个阶段。每个阶段,我们都会面对一个岔路口,我们先随意选一条路走,当发现这条路走不通的时候(不符合期望的解),就回退到上一个岔路口,另选一种走法继续走。

相信看过明日边缘和蝴蝶效应这些电影的人应该很容易去理解回溯,下面就来用回溯思想去分析一下这道题.

3HlYNT.png

3HlO2Q.png

  • 可以看到,以蓝色点递归可以找到所有的组合

  • 但是有一些节点是重复的,因为递归时没有加限制条件,更深一层的递归又会重复去考虑之前已经计算过的组合,所以需要去排序.

  • 排好序之后,当候选数组的元素比目标数还大时,该元素后面的数可以都不用去考虑了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
candidates.sort()
n = len(candidates)
res = []
def helper(start, cur_num, tmp):
if cur_num == 0:
res.append(tmp)
return
# 这里是去重, 排序之后,start前面的元素都不用去考虑了
for i in range(start, n):
# 剪枝,该元素比目标数还大,则直接跳出
# 这里是自下往上组合,上图中是自上往下组合,原理都一样
if cur_num - candidates[i] < 0:
break
helper(i, cur_num - candidates[i], tmp + [candidates[i]])
helper(0, target, [])
return res

复杂度分析

时间复杂度:每一次递归遍历考虑所有可能的组合,所以时间复杂度为$$O(n^2)$$

空间复杂度:O(n)

总结

回溯思想可能是一个时间复杂度较高的算法,很多时候可以用dp去优化,但是在枚举所有可能的结果的时候,就是发挥它的特点的时候了,不要因为复杂度高就不去考虑,所以还是的脚踏实地去学习编程吧!!!

相似题目

组合总和II

组合总和III

全排列

N皇后

CATALOG
  1. 1. 组合总和
    1. 1.1. 回溯思想
      1. 1.1.1. 复杂度分析
      2. 1.1.2. 总结