字符集回溯
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例 1:
输入:digits = “23”
输出:[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
示例 2:
输入:digits = “”
输出:[]
示例 3:
输入:digits = “2”
输出:[“a”,“b”,“c”]
提示:
0 <= digits.length <= 4
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
func letterCombinations(digits string) []string {mappings:=[]string{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}n:=len(digits)ans:=[]string{}if n==0{return []string{}}var dfs func(i int)path:=make([]byte,n,n)dfs=func(i int){if i==n{ans=append(ans,string(path))return}for _,v:=range mappings[digits[i]-'0']{path[i]=byte(v)dfs(i+1)}}dfs(0)return ans
}
78. 子集
给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
选或者不选
func subsets(nums []int) [][]int {var dfs func(i int)ans:=[][]int{}arr:=[]int{}n:=len(nums)dfs=func(i int){if i==n{ans=append(ans,slices.Clone(arr))return}dfs(i+1)arr=append(arr,nums[i])dfs(i+1)arr=arr[:len(arr)-1]}dfs(0)return ans
}
枚举数字
func subsets(nums []int) [][]int {n:=len(nums)ans:=make([][]int,0,1<<n)path:=make([]int,0,n)var dfs func(int)dfs=func(i int){ans=append(ans,slices.Clone(path))for j:=i;j<n;j++{path=append(path,nums[j])dfs(j+1)path=path[:len(path)-1]}}dfs(0)return ans
}
二进制枚举
根据 从集合论到位运算,常见位运算技巧分类总结 中的「枚举子集」的技巧,可以只用简单的循环枚举所有子集。
func subsets(nums []int) [][]int {ans:=make([][]int,1<<len(nums))for i:=range ans{for j,x:=range nums{if i>>j&1==1{ans[i]=append(ans[i],x)}}}return ans
}
131. 分割回文串
给你一个字符串 s,请你将 s 分割成一些 子串,使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例 1:
输入:s = “aab”
输出:[[“a”,“a”,“b”],[“aa”,“b”]]
示例 2:
输入:s = “a”
输出:[[“a”]]
提示:
1 <= s.length <= 16
s 仅由小写英文字母组成
枚举子串结束位置
func isHuiWen(s string)bool{for i,j:=0,len(s)-1;i<=j;i,j=i+1,j-1{if s[i]!=s[j]{return false}}return true
}
func partition(s string) [][]string {var dfs func(i int)n:=len(s)path:=[]string{}ans:=[][]string{}dfs=func(i int){if i==n{ans=append(ans,slices.Clone(path))return}for j:=i;j<n;j++{if isHuiWen(s[i:j+1]){path=append(path,s[i:j+1])dfs(j+1)path=path[:len(path)-1]}}}dfs(0)return ans
}
输入的视角(逗号选或不选)🪝
假设每对相邻字符之间有个逗号,那么就看每个逗号是选还是不选。
也可以理解成:是否要把 s[i] 当成分割出的子串的最后一个字符。注意 s[n−1] 一定是最后一个字符,一定要选。
func isPalindrome(s string, left, right int) bool {for left < right {if s[left] != s[right] {return false}left++right--}return true
}func partition(s string) (ans [][]string) {n := len(s)path := []string{}// 考虑 i 后面的逗号怎么选// start 表示当前这段回文子串的开始位置var dfs func(int, int)dfs = func(i, start int) {if i == n { // s 分割完毕ans = append(ans, slices.Clone(path))return}// 不选 i 和 i+1 之间的逗号(i=n-1 时一定要选)if i < n-1 {// 考虑 i+1 后面的逗号怎么选dfs(i+1, start)}// 选 i 和 i+1 之间的逗号(把 s[i] 作为子串的最后一个字符)if isPalindrome(s, start, i) {path = append(path, s[start:i+1])// 考虑 i+1 后面的逗号怎么选// start=i+1 表示下一个子串从 i+1 开始dfs(i+1, i+1)path = path[:len(path)-1] // 恢复现场}}dfs(0, 0)return
}
组合型回溯+剪枝
77. 组合
给定两个整数 n 和 k,返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1:
输入:n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
示例 2:
输入:n = 1, k = 1
输出:[[1]]
提示:
1 <= n <= 20
1 <= k <= n
枚举下一个数选哪个
func combine(n int, k int) [][]int {var dfs func(i int)ans:=[][]int{}path:=[]int{}dfs=func(i int){path_len:=len(path)if path_len==k{ans=append(ans,slices.Clone(path))return}for j:=i;j>=k-path_len;j--{path=append(path,j)dfs(j-1)path=path[:len(path)-1]}}dfs(n)return ans
}
选或不选🪝
func combine(n, k int) (ans [][]int) {path := []int{}var dfs func(int)dfs = func(i int) {d := k - len(path) // 还要选 d 个数if d == 0 { // 选好了ans = append(ans, append([]int(nil), path...))return}// 如果 i > d,可以不选 iif i > d {dfs(i - 1)}// 选 ipath = append(path, i)dfs(i - 1)path = path[:len(path)-1] // 恢复现场}dfs(n)return
}
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:只使用数字1到9
每个数字 最多使用一次
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。示例 1:输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。
示例 2:输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。
示例 3:输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字,我们可以得到的最小和是1+2+3+4 = 10,因为10 > 1,没有有效的组合。提示:2 <= k <= 9
1 <= n <= 60
func combinationSum3(k int, n int) [][]int {ans:=[][]int{}path:=[]int{}var dfs func(i,sum int)dfs=func(i,sum int){d:=k-len(path)if sum<0||sum>((i*2-d+1)*d)/2{return}if d==0{ans=append(ans,slices.Clone(path))return}for j:=i;j>=d;j--{path=append(path,j)dfs(j-1,sum-j)path=path[:len(path)-1]}}dfs(9,n)return ans
}
选或不选🪝
func combinationSum3(k, n int) (ans [][]int) {path := []int{}var dfs func(int, int)dfs = func(i, t int) {d := k - len(path) // 还要选 d 个数if t < 0 || t > (i*2-d+1)*d/2 { // 剪枝return}if d == 0 { // 找到一个合法组合ans = append(ans, slices.Clone(path))return}// 不选 iif i > d {dfs(i-1, t)}// 选 ipath = append(path, i)dfs(i-1, t-i)path = path[:len(path)-1]}dfs(9, n)return
}
22. 括号生成
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”]
示例 2:
输入:n = 1
输出:[“()”]
提示:
1 <= n <= 8
func generateParenthesis(n int) []string {m:=n*2ans:=[]string{}path:=make([]byte,m)var dfs func(i,open int)dfs=func(i,open int){if i==m{ans=append(ans,string(path))return}if open<n{path[i]='('dfs(i+1,open+1)}if i-open<open{path[i]=')'dfs(i+1,open)}}dfs(0,0)return ans
}
枚举下一个左括号的位置🪝
func generateParenthesis(n int) []string {path:=[]int{}// 记录左括号的下标// i = 目前填了多少个括号// balance = 左括号个数 - 右括号个数var dfs func(int,int)ans:=[]string{}dfs=func(i,balance int){if len(path)==n{s:=bytes.Repeat([]byte{')'},n*2)for _,j:=range path{s[j]='('}ans=append(ans,string(s))return}// 枚举填 close=0,1,2,...,balance 个右括号for close := range balance + 1 {// 先填 close 个右括号,然后填 1 个左括号,记录左括号的下标 i+closepath=append(path,i+close)dfs(i+close+1,balance-close+1)path=path[:len(path)-1]}} dfs(0,0)return ans
}
排列型
46. 全排列
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1:
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2:
输入:nums = [0,1]
输出:[[0,1],[1,0]]
示例 3:
输入:nums = [1]
输出:[[1]]
提示:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
func permute(nums []int) [][]int {n:=len(nums)path:=make([]int,n)onPath:=make([]bool,n)ans:=[][]int{}var dfs func(int)dfs=func(i int){if i==n{ans=append(ans,slices.Clone(path))return}for j,on:=range onPath{if !on{path[i]=nums[j]onPath[j]=truedfs(i+1)onPath[j]=false}}}dfs(0)return ans
}
51. N 皇后
按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案,该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
示例 1:
输入:n = 4
输出:[[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:[[“Q”]]
提示:
1 <= n <= 9
func solveNQueens(n int) [][]string {queens:=make([]int,n)col:=make([]bool,n)diag1:=make([]bool,n*2-1)diag2:=make([]bool,n*2-1)ans:=[][]string{}var dfs func(int)dfs=func(r int){if r==n{board:=make([]string,n)for i,c:=range queens{board[i]=strings.Repeat(".",c)+"Q"+strings.Repeat(".",n-c-1)}ans=append(ans,board)return}//在(r,c)放皇后for c,ok:=range col{rc:=r-c+n-1if !ok&&!diag1[r+c]&&!diag2[rc]{//判断是否能放queens[r]=ccol[c],diag1[r+c],diag2[rc]=true,true,true//占用了c和两条对角线dfs(r+1)col[c],diag1[r+c],diag2[rc]=false,false,false//恢复现场}}}dfs(0)return ans
}