参考：https://leetcode-cn.com/problems/subsets/solution/c-zong-jie-liao-hui-su-wen-ti-lei-xing-dai-ni-gao-/
image.pngimage.png

1、子集、子集 II、组合、组合总和、组合总和 II

A、78子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
image.png

B、90子集 II(剪枝思想)

给定一个可能 包含重复元素 的整数数组 nums，返回该数组所有可能的子集（幂集）。
image.png
需要先排序，跳过重复元素

C、77组合

给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。

D、39组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
image.png

  1. class Solution:
  2.     def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
  3.         result = []
  4.         res=[]
  5.         def dfs(temp,res):
  6.             nonlocal target
  7.             if temp > target:  # 剪枝一:当前的总值大于目标值
  8.                 return
  9.             if temp == target:  # 当前值和目标值相等的时候,保存当前结果,并返回
  10.                 result.append(res)
  11.                 return
  12.             for i in candidates:
  13.                 if res and res[-1] > i:  # 防止重复的方法是,不让其找在当前元素以前的元素
  14.                     continue
  15.                 dfs(temp + i, res + [i])
  16.         dfs(0, res)
  17.         return result

E、40组合总和 II

给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。

2、全排列、全排列 II、字符串的全排列、字母大小写全排列

子集、组合与排列是不同性质的概念。子集、组合是无关顺序的，而排列是和元素顺序有关的，如 [1，2] 和 [2，1] 是同一个组合(子集)，但 [1,2] 和 [2,1] 是两种不一样的排列！！！！因此被分为两类问题

A、46全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

  1. class Solution:
  2.     def permute(self, nums: List[int]) -> List[List[int]]:
  3.         def dfs(path,j):
  4.             if(j==len(nums)):
  5.                 ans.append(path[:])   # 如果有pop语句的话，就必须加上[:]，这是为什么呢
  6.                 return 
  7.             for i in range(len(nums)):
  8.                 if nums[i] not in path:
  9.                     path.append(nums[i])
  10.                     dfs(path,j+1)
  11.                     path.pop(-1)  
  12.         ans=[]
  13.         dfs([],0)
  14.         # print(ans)
  15.         return ans

B、47全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

C、剑38字符串的全排列

输入一个字符串，打印出该字符串中字符的所有排列。

D、784字母大小写全排列

给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

E、87. 扰乱字符串（困难）

等价 951. 翻转等价二叉树
回溯：子集、组合、排列、搜索 - 图6回溯：子集、组合、排列、搜索 - 图7回溯：子集、组合、排列、搜索 - 图8

  1. class Solution:
  2.     @functools.lru_cache(None)
  3.     def isScramble(self, s1: str, s2: str) -> bool:
  4.         N = len(s1)
  5.         if N == 0: return True
  6.         if N == 1: return s1 == s2
  7.         if sorted(s1) != sorted(s2):
  8.             return False
  9.         for i in range(1, N):
  10.             if self.isScramble(s1[:i], s2[:i]) and self.isScramble(s1[i:], s2[i:]):
  11.                 return True
  12.             elif self.isScramble(s1[:i], s2[-i:]) and self.isScramble(s1[i:], s2[:-i]):
  13.                 return True
  14.         return False

有问题、时间超时，每次输入是不一样的无法缓存

  1. class Solution:
  2.     def isScramble(self, s1: str, s2: str) -> bool:
  3.         def dfs(i,j,tmp):
  4.             if sorted(tmp[i:j]) != sorted(s2[i:j]):   # 注意
  5.                 return False
  6.             if tmp[i:j]==s2[i:j]:   # 超时
  7.                 return True
  8.             for m in range(i+1,j):
  9.                 if dfs(i,m,tmp) and dfs(m,j,tmp):
  10.                     return True
  11.                 a=tmp[i:j]  # 注意
  12.                 tmp=tmp[0:i]+tmp[m:j]+tmp[i:m]+tmp[j:len(s1)]
  13.                 if dfs(i,j-m+i,tmp) and dfs(j-m+i,j,tmp):  # 注意
  14.                     return True
  15.                 tmp=tmp[0:i]+a+tmp[j:len(s1)]
  16.             return False
  17.         tmp=s1
  18.         if dfs(0,len(s1),tmp):
  19.             return True
  20.         else:
  21.             return False

3、解数独、单词搜索、N皇后、分割回文串、二进制手表

A、37解数独

B、79单词搜索

和剑指 Offer 12. 矩阵中的路径题目相同
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

  1. class Solution:
  2.     def exist(self, board: List[List[str]], word: str) -> bool:
  3.         row = len(board)
  4.         col = len(board[0])
  6.         def helper(i, j, k, visited):
  7.             #print(i,j, k,visited)
  8.             if k == len(word):    # 终止条件 
  9.                 return True
  10.             for x, y in [(-1, 0), (1, 0), (0, 1), (0, -1)]:   # 选择列表
  11.                 tmp_i = x + i
  12.                 tmp_j = y + j
  13.                 if 0 <= tmp_i < row and 0 <= tmp_j < col and (tmp_i, tmp_j) not in visited \    #   做出选择  
  14.                 and board[tmp_i][tmp_j] == word[k]:
  15.                     visited.add((tmp_i, tmp_j))
  16.                     if helper(tmp_i, tmp_j, k+1, visited):   # 注意，注意！！
  17.                         return True
  18.                     visited.remove((tmp_i, tmp_j))    # 回溯
  19.             return False  
  20.         for i in range(row):
  21.             for j in range(col):
  22.                 if board[i][j] == word[0] and helper(i, j, 1,{(i, j)}) :   #  {(i, j)}
  23.                         return True
  24.         return False

C、51N皇后52N皇后二