0.10 回溯

[46.全排列](https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def backtracking(self, nums, level, res):
        if level == len(nums) - 1:
            res.append(nums[:])
        for i in range(level, len(nums)):
            nums[i], nums[level] = nums[level], nums[i]
            self.backtracking(nums, level+1, res)
            nums[i], nums[level] = nums[level], nums[i]

def permute(self, nums: List[int]) -> List[List[int]]:
        res = []
        self.backtracking(nums, 0, res)
        return res
```
[78. 子集](https://leetcode.cn/problems/subsets/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        res = []
        path = []
        def dfs(i):
            res.append(path.copy())
            for j in range(i, n):
                path.append(nums[j])
                dfs(j+1)
                path.pop()
        dfs(0)
        return res
```
[17. 电话号码的字母组合](https://leetcode.cn/problems/letter-combinations-of-a-phone-number/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        MAP = '', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'
        ans = []
        n = len(digits)
        path = [''] * n
        if n == 0:
            return []
        def dfs(i):
            if i == n:
                ans.append(''.join(path.copy()))
                return
            for c in MAP[int(digits[i])]:
                path[i] = c
                dfs(i+1)
        dfs(0)
        return ans
```
[39. 组合总和](https://leetcode.cn/problems/combination-sum/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        ans = []
        path = []

def dfs(i, remain):
            if remain == 0:
                ans.append(path.copy())
                return
            if i == n or remain < 0:
                return
            dfs(i + 1, remain)
            path.append(candidates[i])
            dfs(i, remain - candidates[i])
            path.pop()

dfs(0, target)
        return ans
```
[22. 括号生成](https://leetcode.cn/problems/generate-parentheses/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        m = 2 * n
        def dfs(s,left,right):
            if len(s) == m:
                res.append(s)
                return
            if left < n:
                dfs(s + '(',left + 1, right)
            if right < left:
                dfs(s + ')', left, right + 1)
        dfs('', 0, 0)
        return res
```
[79. 单词搜索](https://leetcode.cn/problems/word-search/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        def dfs(i, j, k):
            if k == len(word):
                return True
            if not (0 <= i < m and 0 <= j < n and board[i][j] == word[k]):
                return False
            temp = board[i][j]
            board[i][j] = ""
            res = (
                dfs(i + 1, j, k + 1)
                or dfs(i - 1, j, k + 1)
                or dfs(i, j + 1, k + 1)
                or dfs(i, j - 1, k + 1)
            )
            board[i][j] = temp
            return res

for i in range(m):
            for j in range(n):
                if dfs(i, j, 0):
                    return True
        return False
```
[131. 分割回文串](https://leetcode.cn/problems/palindrome-partitioning/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        n = len(s)
        ans = []
        path = []

def dfs(i):
            if i == n:
                ans.append(path.copy())
            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
```