回溯子集型

1. 电话号码的字母组合

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

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

• 输入：digits = "23"
  输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
  ```python
  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 ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

  解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

• 示例 1：

  输入：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

赏

谢谢你请我吃糖果