【Leetcode】刷题之路4（python版）

接上章回溯专题，本章挑选了分割问题、子集问题、排列问题。

• 分割问题
  • 131.分割回文串
  • 93.复原IP地址
• 子集问题
  • 78.子集
  • 90.子集II
• 排列问题
  • 46.全排列
  • 47.全排列II

分割问题

我们来分析一下切割，其实切割问题类似组合问题。

例如对于字符串abcdef：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…

所以切割问题，也可以抽象为一颗树形结构，如下所示：
（图片来源链接：leetcode）

递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。

此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

回溯法搜所有可行解的模板一般是这样的：

res = []
path = []def backtrack(未探索区域, res, path):if 未探索区域满足结束条件:res.add(path) # 深度拷贝returnfor 选择 in 未探索区域当前可能的选择:if 当前选择符合要求:path.add(当前选择)backtrack(新的未探索区域, res, path)path.pop()

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

解题思路

看到题目要求「所有可能的结果」，而不是「结果的个数」，一般情况下，我们就知道需要暴力搜索所有的可行解了，可以用「回溯法」。

「回溯法」实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就「回溯」返回，尝试别的路径。

在每次搜索位置区域的时候，使用的是产生一个新数组 path + [s[:i]] ，这样好处是方便：不同的路径使用的是不同的 path，因此不需要 path.pop() 操作；而且 res.append(path) 的时候不用深度拷贝一遍 path。

class Solution(object):def partition(self, s):self.isPalindrome = lambda s : s == s[::-1] #判断是否时回文字符串res = []self.backtrack(s, res, [])return resdef backtrack(self, s, res, path):if not s: #判断是否str变量为空res.append(path)returnfor i in range(1, len(s) + 1): #注意起始和结束位置if self.isPalindrome(s[:i]):self.backtrack(s[i:], res, path + [s[:i]])#path+[s[:i]] can only concate list to list

时间复杂度：O(N * 2 ^ N)，因为总共有 O(2^N)种分割方法，每次分割都要判断是否回文需要 O(N)O(N) 的时间复杂度。
空间复杂度：O(N ^ 2)，这里不计算返回答案占用的空间的话，数组 f 需要使用的空间为 O(n ^ 2)，而在回溯的过程中，我们需要使用 O(n) 的栈空间以及 O(n) 的用来存储当前字符串分割方法的空间。

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 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：
输入：s = “25525511135”
输出：[“255.255.11.135”,“255.255.111.35”]

示例 2：
输入：s = “0000”
输出：[“0.0.0.0”]

示例 3：
输入：s = “101023”
输出：[“1.0.10.23”,“1.0.102.3”,“10.1.0.23”,“10.10.2.3”,“101.0.2.3”]

解题思路

只要意识到这是切割问题，切割问题就可以使用回溯搜索法把所有可能性搜出来，和刚做过的131.分割回文串就十分类似了。
切割问题可以抽象为树型结构。

切割之后，判断子串是否合法，主要考虑到如下三点：

• 段位以0为开头的数字不合法
• 段位里有非正整数字符不合法
• 段位如果大于255了不合法

回溯三部曲：

• 递归参数
  切割问题类似于组合问题。
  因为不能重复分割，记录下一层递归分割的起始位置startIndex。
  还需要一个变量pointNum，记录添加逗点的数量。

• 递归终止条件
  终止条件和131.分割回文串情况就不同了，本题明确要求只会分成4段作为终止条件，逗点数量为3说明字符串分成了4段。
  然后验证一下第四段是否合法，如果合法就加入到结果集里。

• 单层搜索逻辑
  在 for 循环中，[startIndex, i]这个区间就是截取的子串，需要判断这个子串是否合法。如果合法就在字符串后面加上符号.表示已经分割；如果不合法就结束本层循环，就剪掉该分支。
  然后就是递归和回溯的过程：递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符.），同时记录分割符的数量pointNum 要 +1。回溯的时候，就将刚刚加入的分隔符. 删掉就可以了，pointNum也要-1。

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:res = []path = [] # 存放分割后的字符# 判断数组中的数字是否合法def isValid(p):if p == '0': return True # 解决"0000"if p[0] == '0': return Falseif int(p) > 0 and int(p) <256: return Truereturn Falsedef backtrack(s, startIndex):if len(s) > 12: return  # 字符串长度最大为12if len(path) == 4 and startIndex == len(s): # 确保切割完，且切割后的长度为4res.append(".".join(path[:])) # 字符拼接returnfor i in range(startIndex, len(s)):if len(s) - startIndex > 3*(4 - len(path)): continue # 剪枝，剩下的字符串大于允许的最大长度则跳过p = s[startIndex:i+1] # 分割字符if isValid(p): # 判断字符是否有效path.append(p)else: continuebacktrack(s, i + 1) # 寻找i+1为起始位置的子串path.pop()backtrack(s, 0)return res

子集问题

如果把 子集问题、组合问题、分割问题 都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

其实子集也是一种组合问题，因为它的集合是无序的，子集{1,2} 和 子集{2,1}是一样的。既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始，而不是从0开始！

什么时候for可以从0开始呢？
求排列问题的时候，就要从0开始，因为集合是有序的，{1, 2} 和{2, 1}是两个集合，排列问题我们后续的文章就会讲到的。

以示例中nums = [1,2,3]为例把求子集抽象为树型结构，如下：

（图片来源leetcode代码随想录）

从图中红线部分，可以看出遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合。

78. 子集

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

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

解题思路

求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:res = []  path = []  def backtrack(nums,startIndex):res.append(path[:])  #收集子集，要放在终止添加的上面，否则会漏掉自己for i in range(startIndex,len(nums)):  #当startIndex已经大于数组的长度了，就终止了，for循环本来也结束了，所以不需要终止条件path.append(nums[i])backtrack(nums,i+1)  #递归，每次递归的下一层就是从i+1开始的path.pop()  #回溯backtrack(nums,0)return res

90. 子集II

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

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

解题思路

和78.子集问题中不同的是 怎么去重？

这个去重为什么很难理解呢，所谓去重，其实就是使用过的元素不能重复选取。 这么一说好像很简单！

都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

用示例中的[1, 2, 2] 来举例，如图所示：
注意去重需要先对集合排序
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:res = []  #存放符合条件结果的集合path = []  #用来存放符合条件结果def backtrack(nums,startIndex):res.append(path[:])for i in range(startIndex,len(nums)):if i > startIndex and nums[i] == nums[i - 1]:  #我们要对同一树层使用过的元素进行跳过continuepath.append(nums[i])backtrack(nums,i+1)  #递归path.pop()  #回溯nums = sorted(nums)  #去重需要排序backtrack(nums,0)return res

简化的python写法：

class Solution(object):def subsetsWithDup(self, nums):res = []nums.sort()self.dfs(nums, 0, res, [])return resdef dfs(self, nums, index, res, path):if path not in res: #判断是否已经存在res.append(path)for i in range(index, len(nums)):if i > index and nums[i] == nums[i - 1]:continueself.dfs(nums, i + 1, res, path + [nums[i]])

排列问题

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1]
输出：[[0,1],[1,0]]

解题思路

总结搜索的方法：按顺序枚举每一位可能出现的情况，已经选择的数字在 当前 要选择的数字中不能出现。按照这种策略搜索就能够做到 不重不漏。这样的思路，可以用一个树形结构表示，用回溯的思想来进行深度优先搜索。

class Solution:def permute(self, nums) :res = []def backtrack(nums, path):# nums是未被选中的数的数组# tmp是已经在path中if not nums:res.append(path)return for i in range(len(nums)):backtrack(nums[:i] + nums[i+1:], path + [nums[i]])backtrack(nums, [])return res

47. 全排列II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2], [1,2,1], [2,1,1]]

解题思路

和46.全排列不同的是，该题需要考虑如何去重，去重的概念在本篇的90.子集II已经涉及到。

那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。

那么我们就要优先考虑重复，再思考 回溯的三要素。要强调的是去重一定要对元素经行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。
那么这部分剪枝的条件即为：和前一个元素值相同（此处隐含这个元素的index>0），并且前一个元素还没有被使用过

对于排列问题，树层上去重和树枝上去重，都是可以的，但是树层上去重效率更高重。如下图所示，图片来源leetcode代码随想录。

用输入: [1,1,1] 来举一个例子：

• 树层上去重(used[i - 1] == false) 的树形结构如下：
  
• 树枝上去重(used[i - 1] == true) 的树型结构如下：
  

为什么used[i - 1] == false，说明同一树层nums[i - 1]使用过?

(i>0 && nums[i] == nums[i-1] && used[i-1] == false)

同一树层我的理解是这样，首先看第一个条件 i>0,这个条件的话说明此时已经对第一个位置放的第一个数字的搜索已经完毕，那么下一步要搜索能放在第一个位置的第二个数字，我们已经知道不能放重复的数字，而因为数组已经排序过，相同的数字used[i]都为0，因此通过nums[i] == nums[i-1]可以找到相同的数字。
最后这个条件 used[i-1] == false比较难理解，你可以理解为[1,1,1]中的第一个数字1已经用过一次经历过used[i]的0->1->0的过程变化，所以此时i>0的是判断条件通过进到下一个条件判断，最后到 used[i-1] == false

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:# res用来存放结果        if not nums: return []nums = sorted(nums)#排序res = []used = [0] * len(nums) #是否用过，方便去重def backtracking(nums, used, path):# 终止条件if len(path) == len(nums):res.append(path)res.append(path.copy())returnfor i in range(len(nums)):if not used[i]:if i>0 and nums[i] == nums[i-1] and not used[i-1]:continueused[i] = 1# path.append(nums[i])# backtracking(nums, used, path)backtracking(nums, used, path + [nums[i]])# path.pop()used[i] = 0backtracking(nums,used,[])return res