回溯子集型

2026-02-04

1. 电话号码的字母组合

（17）给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        MAP = ['','','abc','def','ghi','jkl','mno','pqrs','tuv','wxyz']
        n = len(digits)
        res= []
        path = [''] * n
        def dfs(i):
            if i == n:
                res.append(''.join(path))
                return
            for c in MAP[int(digits[i])]:
                path[i] = c
                dfs(i+1)
        dfs(0)
        return res

2 子集

（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 = []
        n = len(nums)
        def subset(index):
            res.append(path.copy())                
            if index == n:
                return
            for i in range(index,n):
                path.append(nums[i])
                subset(i+1)
                path.pop()
        subset(0)
        return res

3. 分割回文串

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

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

class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def huiwen(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)
                    huiwen(j+1)
                    path.pop()
        res = []
        path = []
        n = len(s)
        huiwen(0)
        return res