Fork me on GitHub

回溯系列详解

字数统计: 2.4k字   |   阅读时长≈ 10分

78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例: 

1
2
3
4
5
6
7
8
9
10
11
12
输入: nums = [1,2,3]  
输出:  
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

话不多说，show you the code。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:

# 方法一，迭代思路
        res=[]
        for i in nums:
            # 每遇到一个元素
            for j in range(len(res)):
                # 就在现有子集元素的基础上加上该元素，组成新的子集
                res.append(res[j]+[i])
            res.append([i])
        # 最后补上一个空集
        res.append([])
        return res

#方法一-1，依旧是迭代，用列表推导式的方法更pythonic
        res=[[]]
        for i in nums:
            res+=[[i]+j for j in res ]
        return res
# 方法二、递归
        res = []
        n = len(nums)
        
        def helper(i, tmp):
            res.append(tmp)
            for j in range(i, n):
                helper(j + 1,tmp + [nums[j]] )
        helper(0, [])
        return res

90. 子集 II

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,2]
输出:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]
  • 本题和上一题的唯一区别就在于 nums会出现重复元素。
  • 因此其实做法上只需要增加判断每次迭代或者递归，新的子集元素是否存在于原子集中即可
  • 但是由于解集不能包含重复的子集（相同元素的不同序列，如[1,2,2],[2,1,2]），因此在迭代之前必须对nums进行 排序 操作。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution:
        def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
    # 方法一、递归解法
            if not nums:
                return []
            n = len(nums)
            res = []
            nums.sort()
            def help(idx,tmp_list):

                # 判断tmp_list不在原子集才加入
                if tmp_list not in res:
                    res.append(tmp_list)
                for i in range(idx,n):
                    help(i+1,tmp_list+[nums[i]])
            help(0,[])
            return res
    # 方法二、列表推导式法
            res=[[]]
            for i in sorted(nums):
                # 判断[i]+j不在原子集才加入
                res+=[[i]+j for j in res if [i]+j not in res]
            return res
    # 方法三、迭代法
            res=[]
            nums.sort()
            for i in nums:
                # 每遇到一个元素
                for j in range(len(res)):
                    # 判断res[j]+[i]不在原子集才加入
                    if res[j]+[i] not in res:
                    # 就在现有子集元素的基础上加上该元素，组成新的子集
                        res.append(res[j]+[i])
                if [i] not in res:
                    res.append([i])
            # 最后补上一个空集
            res.append([])
            return res

39. 组合总和

给定一个无重复元素的数组candidates 和一个目标数 target，找出candidates中所有可以使数字和为target的组合。
candidates 中的数字可以无限制重复被选取。
说明：

  • 所有数字（包括 target ）都是正整数。
  • 解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

示例 2:

1
2
3
4
5
6
7
输入: candidates = [2,3,5], target = 8,
所求解集为:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

本题的总体思路是回溯+剪枝

  • 以 target = 7 为根结点，每一个分支做减法。
  • 减到 0 或者负数的时候，剪枝。其中，减到 0 的时候结算，这里 “结算” 的意思是添加到结果集。


上图说明：
一个蓝色正方形表示的是 “尝试将这个数到数组 candidates 中找组合”，那么怎么找呢？挨个减掉那些数就可以了。

  • 在减的过程中，会得到 0 和负数，也就是被我标红色和粉色的结点：

    • 得到 0 是我们喜欢的，从 0 这一点向根结点走的路径（很可能只走过一条边，也算一个路径），就是一个组合，在这一点要做一次结算（把根结点到 0 所经过的路径，加入结果集）。
    • 得到负数就说明这条路走不通，没有必要再走下去了。

总结一下：在减的过程中，得到 0 或者负数，就没有必要再走下去，所以这两种情况就分别表示成为叶子结点。此时递归结束，然后要发生回溯。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        # 先将candidates进行排序，避免后面剪枝的时候出现如[2, 2, 3], [2, 3, 2]这样的重复路径
        # 要排序的理由：1、前面用过的数后面不能再用；2、下一层边上的数不能小于上一层边上的数。
        candidates.sort()
        res=[]
        path=[]
        n=len(candidates)
        def dfs(start,target):
            # 递归终止条件，Python 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
            if target==0:
                print(path)
                print(path[:])
                res.append(path[:])
            for i in range(start,n):
                tmp= target-candidates[i]
                if tmp<0:break
                path.append(candidates[i])
                # 因为下一层不能比上一层还小，起始索引还从 index 开始
                dfs(i,tmp)
                path.pop()
        dfs(0,target)
        return res

40. 组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明：

所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

示例 2:

1
2
3
4
5
6
输入: candidates = [2,5,2,1,2], target = 5,
所求解集为:
[
  [1,2,2],
  [5]
]

思路

  • 本题和上题的区别在于candidates中的元素不可重复使用
  • 因此只需要在递归的时候每层dfs从下一个元素开始即可
  • 因为本身candidates中有重复元素，因此path在加入res之前需要查重

话不多说，show you the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        if not candidates:
            return []
        res=[]
        path=[]
        candidates.sort()
        n=len(candidates)

        def dfs(start,target):
            #与上题区别一、 去重
            if target==0 and path[:] not in res:
                res.append(path[:])
            for i in range(start,n):
                tmp=target-candidates[i]
                if tmp<0:
                    break
                path.append(candidates[i])
                #与上题区别二、 从下一个元素开始dfs
                dfs(i+1,tmp)
                path.pop()
        dfs(0,target)
        return res

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

  • 所有数字都是正整数。
  • 解集不能包含重复的组合。
    示例 1:
    1
    2
    输入: k = 3, n = 7
    输出: [[1,2,4]]

示例 2:

1
2
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

思路

  • 本题和前两题的区别在于candidates变成了[1,2,3,4,5,6,7,8,9],且path长度只能是k,candidates不可重复使用
  • 因此只需要在递归的时候每层dfs从下一个元素开始即可，并且在加入path之前，确认path的长度是否为k

话不多说，show you the code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        # 排除k=0,n=0和k<n的情况
        if k==0 or n==0 or k>n:
            return []
        res,path=[],[]
        def helper(start,target):
            # 当此时target=0且path长度为k时，加入path
            if target==0 and len(path)==k:
                res.append(path[:])
            for i in range(start,10):
                tmp=target-i
                # 剪枝
                if tmp<0:
                    break
                path.append(i)
                # 从下一个开始继续dfs
                helper(i+1,tmp)
                print(path,i)
                path.pop()
        helper(1,n)
        return res

46. 全排列

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

1
2
3
4
5
6
7
8
9
10
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

思路

  • 回溯，详情见代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    # 方法一
    class Solution:
        def permute(self, nums: List[int]) -> List[List[int]]:
            if not nums: return []
            res=[]
            n=len(nums)
            # 使用vis数组保存访问过的元素
            vis=[0]*n
            def backtrack(tmp_list):
                if len(tmp_list)==n:
                    res.append(tmp_list)
                for i in range(n):
                    # 访问过的直接跳过
                    if vis[i]:
                        continue
                    # 状态置为已访问，并将tmp_list加上当前元素继续递归
                    vis[i]=1
                    backtrack(tmp_list+[nums[i]])
                    # 将访问状态初始化，才不会影响别的路径
                    vis[i]=0
            backtrack([])
            return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 方法二
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        res=[]
        n=len(nums)

        def backtrack2(nums,tmp_list):
            if not nums:
                res.append(tmp_list)
            for i in range(len(nums)):
                # 每次访问过后将i从nums中去除，节省了vis记录访问的空间
                backtrack2(nums[:i]+nums[i+1:],tmp_list+[nums[i]])
        backtrack2(nums,[])
        return res

47. 全排列 II

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

1
2
3
4
5
6
7
输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路：

  • 本题和上题的区别在于nums会出现重复元素，这个导致全排列子集需要去重
  • 因此本题的难点在于如何去重剪枝
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 方法一、朴素思想
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        res=[]
        def backtrack(nums,tmp_list):
            # 最简单的想法，只需要在tmp_list加入之前判断是否存在于res
            # 但是数组的查找效率为O(N)，因此导致算法整体速度大大下降 
            if not nums and tmp_list not in res:
                res.append(tmp_list)
            for i in range(len(nums)):
                backtrack(nums[:i]+nums[i+1:],tmp_list+[nums[i]])
        backtrack(nums,[])
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 方法二、记录已访问元素
class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        if not nums: return []
        res=[]
        def backtrack(nums,tmp_list):
            # 在递归的开始创建一个空集合
            vis=set()
            if not nums:
                res.append(tmp_list)
            for i in range(len(nums)):
                # 遍历元素的时候，如果该元素在vis中存在，则进行剪枝跳过，否则加入vis
                # 由于set的查找效率为O(1)因此运行速度大大提升
                if nums[i] in vis:
                    continue
                else:
                    vis.add(nums[i])
                backtrack(nums[:i]+nums[i+1:],tmp_list+[nums[i]])
        backtrack(nums,[])
        return res
赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia-plus根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

北京邮电大学计算机硕士，研究方向：
Python、机器学习、深度学习
计算机视觉、NLP。

联系QQ:443563098

只做了一点微小的工作
谢谢大家