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，可以不选 i
        if i > d {
            dfs(i - 1)
        }

        // 选 i
        path = 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
        }
        
        // 不选 i
        if i > d {
            dfs(i-1, t)
        }
        
        // 选 i
        path = 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*2
    ans:=[]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+close
            path=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]=true
                dfs(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-1
            if !ok&&!diag1[r+c]&&!diag2[rc]{//判断是否能放
                queens[r]=c
                col[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
}