力扣系列题,回溯专场

力扣系列题

https://leetcode.cn/problems/permutations/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liweiw/

做回溯的最关键的问题：1、递归参数是什么，2、终止条件是什么
46. 全排列（中等）
47. 全排列 II（中等）：思考为什么造成了重复，如何在搜索之前就判断这一支会产生重复；
39. 组合总和（中等）
40. 组合总和 II（中等）
77. 组合（中等）
78. 子集（中等）
90. 子集 II（中等）：剪枝技巧同 47 题、39 题、40 题；
60. 第 k 个排列（中等）：利用了剪枝的思想，减去了大量枝叶，直接来到需要的叶子结点；
93. 复原 IP 地址（中等）

注意如下模板复杂度比较高，时间复杂度和空间复杂度均为O(N*N!)

全排列

46. 全排列
    给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

递归参数为数组中是否被使用的标志
终止条件为path的大小等于nums

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        path = []
        res = []
        def dfs(used):
            if len(path) == len(nums):
                res.append(path[:])
            for j in range(len(nums)):
                if used[j] == True: continue
                path.append(nums[j])
                used[j] = True
                dfs(used)
                path.pop()
                used[j] = False
        used = [False for _ in range(len(nums))]
        dfs(used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

47. 全排列 II
    给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

需要对重复的排列进行剪枝
与上题的唯一差异就在于多了剪枝判断

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        used = [False for _ in range(len(nums))]
        path = []
        res = []

        def dfs(used):
            if len(path) == len(nums): 
                res.append(path[:])
                return
            for i in range(len(nums)):
                if used[i]: continue
                if i>0 and nums[i] == nums[i-1] and used[i-1] == False: continue
                path.append(nums[i])
                used[i] = True
                dfs(used)
                used[i] = False
                path.pop()
        used = [False for _ in range(len(nums))]
        nums.sort()
        dfs(used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

组合

77. 组合
    给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

直接递归就可以

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        path = []
        def dfs(i):
            if len(path) == k:
                res.append(path[:])
            for j in range(i,n+1):
                path.append(j)
                dfs(j+1)
                path.pop()
        dfs(1)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13

39. 组合总和
    给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
    candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
    对于给定的输入，保证和为 target 的不同组合数少于 150 个

递归和dp相辅相成，此题既可以用递归暴力，也可以使用dp来求解。但是注意的是，dp返回的是组合的数量，无法返回组合分别是什么
递归参数：target
终止条件： target==0
难点是在于如何对重复的结果进行剪枝,保持有序搜索，在搜索的过程中去重

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        def dfs(j,target):
            if target == 0: 
                res.append((path[:]))
            if target<0: return 
            for i in range(j,len(candidates)):
                path.append(candidates[i])
                dfs(i,target - candidates[i])
                path.pop()
        dfs(0,target)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14

40. 组合总和 II
    给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
    candidates 中的每个数字在每个组合中只能使用 一次 。

是用排序+used来剔除重复遍历的情况，由于是每个数字只能使用一次，所以递归参数为j+1而非上一题的j。

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        path = []
        res = []
        def dfs(i,target,used):
            if target == 0:
                res.append(path[:])
                return
            if target <0:
                return
            for j in range(i,len(candidates)):
                if j>0 and candidates[j] == candidates[j-1] and used[j-1] == False: continue
                path.append(candidates[j])
                used[j] = True
                dfs(j+1,target-candidates[j],used)
                path.pop()
                used[j] = False
        candidates = sorted(candidates)
        used = [False for _ in range(len(candidates))]
        dfs(0,target,used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

216. 组合总和 III
     找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res  = []
        path = []
        def dfs(i):
            if sum(path) == n and len(path) == k:
                res.append(path[:])
                return 
            if len(path)>=k: return 
            for j in range(i,10):
                path.append(j)
                dfs(j+1)
                path.pop()
        dfs(1)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

377. 组合总和 Ⅳ
     给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

这题也可以利用递归来求解，但是时间复杂度太高。可以通过dp的方式快速求解得到
使用dp时要注意内外层循环，外层时targte，内层时nums，直接使用一维dp即可

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        res = []
        path = []
        def dfs(i,target):
            if target == 0: 
                res.append(path[:])
                return
            if target<0:
                return 
            for j in range(len(nums)):
                path.append(nums[j])
                dfs(j,target - nums[j])
                path.pop()
        dfs(0,target)
        return len(res)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        dp = [0 for _ in range(target+1)]
        dp[0] = 1
        for j in range(target+1):
            for i in range(len(nums)):
                if j-nums[i]>=0:
                    dp[j] += dp[j-nums[i]]
        return dp[-1]
1
2
3
4
5
6
7
8
9

78. 子集
    给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
    解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        res = []
        def dfs(i,path):
            res.append(path[:])
            for j in range(i,len(nums)):
                path.append(nums[j])
                dfs(j+1,path)
                path.pop()
        dfs(0,[])
        return res
1
2
3
4
5
6
7
8
9
10
11

90. 子集 II
    给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

剪枝，去重，和之前的处理策略是一致的

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        res = []
        used = [False for _ in range(len(nums))]
        def dfs(i,path,used):
            res.append(path[:])
            for j in range(i,len(nums)):
                if j>0 and nums[j] == nums[j-1] and used[j-1]  == False: continue
                path.append(nums[j])
                used[j] = True
                dfs(j+1,path,used)
                path.pop()
                used[j] = False
        nums = sorted(nums)
        dfs(0,[],used)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

60. 排列序列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”
给定 n 和 k，返回第 k 个排列。

也可以套用上述模板，使用used来去重，但是这样做会超时

class Solution:
    def getPermutation(self, n: int, k: int) -> str:
        res = []
        path = []
        used = [False for _ in range(n+1)]
        def dfs(i,used):
            if len(path) == n:
                res.append(path[:])
            for j in range(1,n+1):
                if used[j]: continue
                path.append(str(j))
                used[j] = True
                dfs(j+1,used)
                path.pop()
                used[j] = False
        dfs(0,used)
        #print(res)
        return ''.join(res[k-1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 ‘.’ 分隔。

例如：“0.1.2.201” 和 “192.168.1.1” 是 有效 IP 地址，但是 “0.011.255.245”、“192.168.1.312” 和 “192.168@1.1” 是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 ‘.’ 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

这题难点就在于理清dfs的逻辑
1、递归参数：ids:表示第几个addr， idx表示在哪个数位
2、终止条件，ids为4且idx遍历完输入数组
3、分四种情况讨论
如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
一般情况，枚举每一种可能性并递归

class Solution:
    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s)<4 or len(s)>12: return []
        total_len = 4
        segment = [0] * 4
        res =[]
        def dfs(ids, idx):
        	# 如果找到了 4 段 IP 地址并且遍历完了字符串，那么就是一种答案
            if ids == 4:
                if idx == len(s):
                    res.append('.'.join(str(seg) for seg in segment))
                return 
            # 如果还没有找到 4 段 IP 地址就已经遍历完了字符串，那么提前回溯
            if idx == len(s): return 
            
            # 由于不能有前导零，如果当前数字为 0，那么这一段 IP 地址只能为 0
            if s[idx] == '0':
                segment[ids] = 0
                dfs(ids + 1, idx+1)
			# 一般情况，枚举每一种可能性并递归
			addr = 0
            for end in range(idx,len(s)):
                addr = 10*addr + int(s[end])
                if 0< addr<= 255:
                    segment[ids] = addr
                    dfs(ids+1, end+1)
                else:
                    break
        dfs(0,0)
        return res
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