文章目录
- 4.8 回溯（基础题-子集问题）
- 17. 电话号码的字母组合
- 78. 子集
- 131. 分割回文串
4.8 回溯（基础题-子集问题）
回溯——一个很有趣的解决问题的办法，这回好好学一次。也有是模板可以模范的，今天我忽然在想，即便再复杂的数据结构也是有其基础的，其基础或许就是这些简单思维的拼接，所以大道至简。
17. 电话号码的字母组合
题目链接
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2：
输入：digits = “”
输出：[]
示例 3：
输入：digits = “2”
输出：[“a”,“b”,“c”]
提示：
- 0 <= digits.length <= 4
- digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
MAPPING = "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz""""时间复杂度：O(n*4^n)，其中n为digits的长度。最坏情况下每次需要枚举4个字母，空间复杂度：O(n)"""
class Solution:def letterCombinations(self, digits: str) -> List[str]:n = len(digits)if(n==0): return []ans = []path = [''] * ndef dfs(i: int) -> None:if i == n:ans.append(''.join(path))return for c in MAPPING[int(digits[i])]:path[i] = c dfs(i+1)dfs(0)return ans78. 子集
题目链接
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0]
输出：[[],[0]]
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
- nums 中的所有元素 互不相同
这道题有两个不好理解的地方：第一个是代码中的状态恢复，需要保证回溯过程中始终维持一个原始的状态，则添加了什么就对应的去除什么（具体看代码）；第二个是代码中的path的使用，也很有趣，其实就是第一个的具体表现。
class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:"""时间复杂度：O(n*2^n)，其中n为nums的长度。答案的长度为子集的个数，即2^n，同时每次递归都把一个数组放入答案，因此会递归2^n次，再算上加入答案时复制path需要O(n)的时间，空间复杂度：O(1)。返回值的空间不计。有的代码 path 长度会预先分配好，这种情况下不需要恢复现场，因为会直接覆盖已经填入的数据。如果 path 初始化成空列表的话，会不断往 path 末尾添加数据，这种情况是需要恢复现场的，如果不恢复现场，path 就会越来越长，不满足要求。"""n = len(nums)ans = []path = []def dfs(i: int) -> None:ans.append(path.copy())for j in range(i,n):path.append(nums[j])dfs(j+1)path.pop()dfs(0)return ans131. 分割回文串
题目链接
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1：
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2：
输入：s = “a”
输出：[[“a”]]
提示：
- 1 <= s.length <= 16
- s 仅由小写英文字母组成
class Solution:def partition(self, s: str) -> List[List[str]]:"""时间复杂度：O(n*2^n)，其中n为nums的长度。答案的长度为子集的个数，即2^n，同时每次递归都把一个数组放入答案，因此会递归2^n次，再算上加入答案时复制path需要O(n)的时间，空间复杂度：O(1)。返回值的空间不计。"""ans = []path = []n = len(s)def dfs(i):if i == n: ans.append(path.copy())return for j in range(i,n):t = s[i:j+1]if t == t[::-1]:path.append(t)dfs(j+1)path.pop()dfs(0)return ans
