【2025力扣打卡系列】子集型回溯

坚持按题型打卡&刷&梳理力扣算法题系列，语言为python3，Day1

• 子集型回溯
  • 每个元素都可以选或者不选
  • 站在输入的角度，每个数/字母可以在子集中（选），也可以不在子集中（不选），叶子是答案 ；那么当前操作就是枚举第 i 个数是选还是不选，子问题就是从 i+1 中构造子集
  • dfs（i）——》dfs（i+1）
  • 思路代码：
    • 非边界条件
      • 不选的话就直接跳过，也就是直接dfs（i+1）
      • 选的话就先加到路径中，即path.append(nums[i])，再递归dfs（i+1）
      • 注意恢复现场：即在返回之前，要恢复成递归之前的样子，即path.pop()
    • 边界条件
      • 把当前路径中记录的答案加到ans中，即ans.append(path.copy()) #注意：由于此处的path是全局变量，是会变化的，所以此处要写path.copy()将答案固定下来

电话号码的字母组合

• 题目描述
  

• 解题思路

  • 用一个path数组记录路径上的字母
  • 在树上做深搜 dfs（i）——》dfs（i+1）当前操作——〉下一个子问题
  • 生成的字符串长度和输入的字符串长度是一致的（即路径path是一个长度为n的数组）
  • 若digits长度为0则直接返回空数组
  • 初始化答案数组ans为空

• 代码参考

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 []ans