golang算法回溯

字符集回溯

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
}