回溯（子集型）：分割回文串

一、多维递归 -> 回溯

1.1：17. 电话号码的字母组合(力扣hot100）

• 代码：

mapping = ["","", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
class Solution:def letterCombinations(self, digits: str) -> List[str]:n = len(digits)if n == 0:return []res = []path = [""] * ndef dfs(i):                              # 一个子问题的具体细节if i==n:res.append("".join(path))returnfor c in mapping[int(digits[i])]:path[i] = cdfs(i+1)                       # 下一个子问题dfs(0)return res

二、子集型回溯

2.1：78. 子集

• 代码：

class Solution:'''站在输入的角度，每个数都可选或不选最终每个叶子就是答案'''def subsets(self, nums: List[int]) -> List[List[int]]:if len(nums) == 0:return []res = []path = []n = len(nums)def dfs(i):if i==n:res.append(path.copy())returndfs(i+1)                # 不选path.append(nums[i])    # 选dfs(i+1)path.pop()   # 记得恢复现场dfs(0)return resclass Solution:"""站在答案的角度，第一个数选谁，第二个数选谁,...每个节点都是答案子集"""def subsets(self, nums: List[int]) -> List[List[int]]:if len(nums) == 0:return []res = []path = []n = len(nums)def dfs(i):res.append(path.copy())  # 每个节点都直接添加if i==n:returnfor j in range(i, n):path.append(nums[j])    # 下一个数选谁dfs(j+1)path.pop()   # 记得恢复现场dfs(0)return res

2.2：131. 分割回文串

• 代码：

class Solution:"""站在答案的角度，第一个数选谁，第二个数选谁,...每个节点都是答案"""def partition(self, s: str) -> List[List[str]]:res = []path = []n = len(s)def dfs(i):if i==n:res.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 res