回溯

1. 回溯简介

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。

回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。
因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。
递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯模板：

可以将回溯看成一个N叉树。
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

2. 题目分类

3. 组合问题

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

题解概要：

1.组合问题是典型的回溯问题。相当于一个N叉树的遍历取值。其中，数组的宽度是N叉树的宽度，递归的深度是N叉树的深度。

代码：

func combine(n int, k int) [][]int {
    ans := [][]int{}
    var dfs func(int,[]int)
    dfs = func(start int,path []int){
        if len(path) == k{
            tmp := make([]int,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
            return
        }
        //剪枝
        if len(path)+n-start+1 < k{
            return 
        }
        for i := start;i <= n;i++{
            path = append(path,i)
            dfs(i+1,path)
            path = path[:len(path)-1]
        }
    }
    dfs(1,[]int{})
    return ans
}

216. 组合总和 III 中等

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：
所有数字都是正整数。
解集不能包含重复的组合。

示例 1:
输入: k = 3, n = 7
输出: [[1,2,4]]

示例 2:
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]

题解概要：

1.组合问题是典型的回溯问题。相当于一个N叉树的遍历取值。其中，数组的宽度是N叉树的宽度，递归的深度是N叉树的深度。

代码：

func combinationSum3(k int, n int) [][]int {
    ans := [][]int{}
    var dfs func(int,int,[]int)
    dfs = func(start int,sum int,path []int){
        if len(path) == k && sum == n{
            tmp := make([]int,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
            return
        }
        //剪枝
        if len(path)+n-start+1 < k || sum > n{
            return
        }
        for i := start;i<=9;i++{
            path = append(path,i)
            sum+=i
            dfs(i+1,sum,path)
            sum-=i
            path = path[:len(path)-1]
        }
    }
    dfs(1,0,[]int{})
    return ans
}

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’] 的一个数字。

题解概要：

1.这道题也是组合问题。但index代表的含义不同，且N叉树的宽度不再是数组宽度了，而是每个数字在键盘上对应的字母数量。

代码：

func letterCombinations(digits string) []string {
    ans := []string{}
    n := len(digits)
    if n == 0{
        return ans
    }
    m := [10]string{
        "",
        "",
        "abc",
        "def",
        "ghi",
        "jkl",
        "mno",
        "pqrs",
        "tuv",
        "wxyz",
    }
    var dfs func(int,[]byte)
    dfs = func(index int,path []byte){
        //满足条件
        if index == n{
            tmp := make([]byte,len(path))
            copy(tmp,path)
            ans = append(ans,string(tmp))
            return
        }
        //找到当前数字对应的键盘字符数组
        letters := m[digits[index]-'0']
        //遍历字符数组
        for i := 0;i < len(letters);i++{
            path = append(path,letters[i])
            dfs(index+1,path)
            path = path[:len(path)-1]
        }
    }
    dfs(0,[]byte{})
    return ans
}

39. 组合总和 中等

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• candidate 中的每个元素都 互不相同
• 1 <= target <= 500

题解概要：

1.这道题也是组合问题。由于可以重复选择元素，因此每次递归时，i不需要+1.

代码：

func combinationSum(candidates []int, target int) [][]int {
    ans := [][]int{}
    var dfs func(int,int,[]int)
    dfs = func(start int,sum int,path []int){
        if sum > target{
            return
        }
        if sum == target{
            tmp := make([]int,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
            return
        }
        for i := start;i < len(candidates);i++{
            path = append(path,candidates[i])
            sum += candidates[i]
            dfs(i,sum,path)
            sum -= candidates[i]
            path = path[:len(path)-1]
        }
    }
    dfs(0,0,[]int{})
    return ans
}

40. 组合总和 II 中等

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。

示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]

示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出: [ [1,2,2], [5] ]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

题解概要：

1.这道题也是组合问题。但是要注意去重，去重的逻辑需梳理清楚。

代码：

func combinationSum2(candidates []int, target int) [][]int {
    ans := [][]int{}
    sort.Ints(candidates)
    var dfs func(int,int,[]int)
    dfs = func(start int,sum int,path []int){
        if sum > target{
            return
        }
        if sum == target{
            tmp := make([]int,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
            return
        }
        for i := start;i < len(candidates);i++{
            //去重开始
            if i > start && candidates[i] == candidates[i-1]{
                continue
            }
            path = append(path,candidates[i])
            sum += candidates[i]
            dfs(i+1,sum,path)    //由于每个数字都不能重复,因此i+1
            sum -= candidates[i]
            path = path[:len(path)-1]
        }
    }
    dfs(0,0,[]int{})
    return ans
}

4.子集、排列问题

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 中的所有元素 互不相同

题解概要：

1.子集问题其实是找N叉树上的所有节点。组合问题是找N叉树上的叶子节点。

代码：

func subsets(nums []int) [][]int {
    ans := [][]int{}
    var backTracking func(int,[]int)
    backTracking = func(start int,path []int){
        //加入子集
        tmp := make([]int,len(path))
        copy(tmp,path)
        ans = append(ans,tmp)
        //终止条件  
        if start == len(nums){
            return
        }
        //回溯
        for i := start;i < len(nums);i++{
            path = append(path,nums[i])
            backTracking(i+1,path)
            path = path[:len(path)-1]
        }
    }
    backTracking(0,[]int{})
    return ans
}

90. 子集 II 中等

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：
输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10

题解概要：

1.子集问题其实是找N叉树上的所有节点。组合问题是找N叉树上的叶子节点。这道题要注意如何去重，和40题去重逻辑是一致的。

代码：

func subsetsWithDup(nums []int) [][]int {
    ans := [][]int{}
    sort.Ints(nums)
    var backTracking func(int,[]int)
    backTracking = func(start int,path []int){
        //加入子集
        tmp := make([]int,len(path))
        copy(tmp,path)
        ans = append(ans,tmp)
        //终止条件  
        if start == len(nums){
            return
        }
        //回溯
        for i := start;i < len(nums);i++{
            if i > start && nums[i] == nums[i-1]{
                continue
            }
            path = append(path,nums[i])
            backTracking(i+1,path)
            path = path[:len(path)-1]
        }
    }
    backTracking(0,[]int{})
    return ans
}

491. 递增子序列 中等

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。
数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：
输入：nums = [4,4,3,2,1]
输出：[[4,4]]

提示：

• 1 <= nums.length <= 15
• -100 <= nums[i] <= 100
• 
  

题解概要：

这道题和子集问题很像。但是去重逻辑不能和90题一样。可以在每一层都定义一个散列表来标明数字是否在同一层已被使用。

代码：

func findSubsequences(nums []int) [][]int {
    ans := [][]int{}
    var backTracking func(int,[]int)
    backTracking = func(start int,path []int){
        if len(path) > 1{
            tmp := make([]int,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
        }
        used := [201]int{}
        for i := start;i < len(nums);i++{
            //同一树层去重逻辑。
            if (len(path) > 0 && nums[i] < path[len(path)-1]) || used[nums[i]+100] == 1{
                continue
            }
            path = append(path,nums[i])
            used[nums[i]+100] = 1
            backTracking(i+1,path)
            path = path[:len(path)-1]
        }
    }
    backTracking(0,[]int{})
    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 中的所有整数 互不相同

题解概要：

1.子集问题其实是找N叉树上的所有节点。组合和排列问题是找N叉树上的叶子节点。但和组合不一样的是，排列中数是有序的，因此每次遍历时，都要从0开始，而不是从start开始。同时也需要用一个used数组标记数字是否被使用过。

代码：

func permute(nums []int) [][]int {
    ans := [][]int{}
    used := make([]bool,len(nums))
    var backTracking func([]int,[]bool)
    backTracking = func(path []int,used []bool){
        if len(path) == len(nums){
            tmp := make([]int,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
            return
        }
        for i := 0;i < len(nums);i++{
            if used[i]{
                continue
            }
            path = append(path,nums[i])
            used[i] = true
            backTracking(path,used)
            path = path[:len(path)-1]
            used[i] = false
        }
    }
    backTracking([]int{},used)
    return ans
}

47. 全排列 II 中等

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

示例 1：
输入：nums = [1,1,2]
输出： [[1,1,2], [1,2,1], [2,1,1]]

示例 2：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

题解概要：

1.子集问题其实是找N叉树上的所有节点。组合和排列问题是找N叉树上的叶子节点。但和组合不一样的是，排列中数是有序的，因此每次遍历时，都要从0开始，而不是从start开始。同时也需要用一个used数组标记数字是否被使用过。这里又涉及到去重，因此要将数组进行排序。

代码：

func permuteUnique(nums []int) [][]int {
    ans := [][]int{}
    sort.Ints(nums)
    used := make([]bool,len(nums))
    var backTracking func([]int,[]bool)
    backTracking = func(path []int,used []bool){
        if len(path) == len(nums){
            tmp := make([]int,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
            return
        }
        for i := 0;i < len(nums);i++{
            //在同一树层上去重的逻辑
            if i > 0 && nums[i] == nums[i-1] && used[i-1] == false{
                continue
            }
            //used[i] = true，说明同一递归树上元素已经被使用。
            if used[i] == false{
                path = append(path,nums[i])
                used[i] = true
                backTracking(path,used)
                path = path[:len(path)-1]
                used[i] = false
            }
        }
    }
    backTracking([]int{},used)
    return ans
}

5. 矩阵中的回溯

面试题 08.02. 迷路的机器人 中等

设想有个机器人坐在一个网格的左上角，网格 r 行 c 列。机器人只能向下或向右移动，但不能走到一些被禁止的网格（有障碍物）。设计一种算法，寻找机器人从左上角移动到右下角的路径。

网格中的障碍物和空位置分别用 1 和 0 来表示。
返回一条可行的路径，路径由经过的网格的行号和列号组成。左上角为 0 行 0 列。如果没有可行的路径，返回空数组。

示例 1:
输入:
[
[0,0,0],
[0,1,0],
[0,0,0]
]
输出: [[0,0],[0,1],[0,2],[1,2],[2,2]]
解释:
输入中标粗的位置即为输出表示的路径，即
0行0列（左上角） -> 0行1列 -> 0行2列 -> 1行2列 -> 2行2列（右下角）
说明：r 和 c 的值均不超过 100。

题解概要：

1.使用回溯模板，这道题最重要的是进行剪枝，因为递归越深效率越低，使用剪枝可以大大提高效率。要标记格子是否被使用过。

代码：

func pathWithObstacles(obstacleGrid [][]int) [][]int {
    ans := [][]int{}
    if len(obstacleGrid) == 0 || len(obstacleGrid[0]) == 0{
        return ans
    }
    n := len(obstacleGrid)
    m := len(obstacleGrid[0])
    if obstacleGrid[0][0] == 1 || obstacleGrid[n-1][m-1] == 1{
        return ans
    }
    var backTracking func(int,int,[][]int)
    backTracking = func(r int,c int,path [][]int){
        if r >= n || c >= m || obstacleGrid[r][c] != 0 || len(ans) != 0 {
            return
        }
        if r == n-1 && c == m-1{
            tmp := make([][]int,len(path))
            copy(tmp,path)
            ans = tmp
            return 
        }
        obstacleGrid[r][c] = 2  //将访问过的格子标记一下，避免重复访问。
        //向右
        if c+1 < m && obstacleGrid[r][c+1] == 0{
            path = append(path,[]int{r,c+1})
            backTracking(r,c+1,path)
            path = path[:len(path)-1]
        }
        //向下
        if r+1 < n && obstacleGrid[r+1][c] == 0{
            path = append(path,[]int{r+1,c})
            backTracking(r+1,c,path)
            path = path[:len(path)-1]
        }
    }
    backTracking(0,0,[][]int{[]int{0,0}})
    return ans
}

1219. 黄金矿工 中等

你要开发一座金矿，地质勘测学家已经探明了这座金矿中的资源分布，并用大小为 m * n 的网格 grid 进行了标注。每个单元格中的整数就表示这一单元格中的黄金数量；如果该单元格是空的，那么就是 0。
为了使收益最大化，矿工需要按以下规则来开采黄金：

• 每当矿工进入一个单元，就会收集该单元格中的所有黄金。
• 矿工每次可以从当前位置向上下左右四个方向走。
• 每个单元格只能被开采（进入）一次。
• 不得开采（进入）黄金数目为 0 的单元格。
• 矿工可以从网格中 任意一个 有黄金的单元格出发或者是停止。

示例 1：
输入：grid = [[0,6,0],[5,8,7],[0,9,0]]
输出：24
解释： [[0,6,0], [5,8,7], [0,9,0]] 一种收集最多黄金的路线是：9 -> 8 -> 7。

示例 2：
输入：grid = [[1,0,7],[2,0,6],[3,4,5],[0,3,0],[9,0,20]]
输出：28
解释： [[1,0,7], [2,0,6], [3,4,5], [0,3,0], [9,0,20]] 一种收集最多黄金的路线是：1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7。

提示：

• 1 <= grid.length, grid[i].length <= 15
• 0 <= grid[i][j] <= 100
• 最多 25 个单元格中有黄金。

代码：

var max int // 最终结果
func getMaximumGold(grid [][]int) int {
    // 记录单元格是否被访问
    visited := make([][]bool, len(grid))
    for k := range visited {
        visited[k] = make([]bool, len(grid[0]))
    }
    max = 0
    // 以每一个有黄金的单元格为起点开始搜索
    for row, v := range grid {
        for col, v1 := range v {
            if v1 != 0 {
                backTrack(row, col, 0, grid, visited)
            }
        }
    }
    return max
}
// row/col 当前的行列 sum 当前的累加黄金 grid 金矿黄金分布 visited单元格访问数组
func backTrack(row, col int, sum int, grid [][]int, visited [][]bool) {
    // 越界/无黄金/已访问 情况排除
    if row < 0 || row >= len(grid) || col < 0 || col >= len(grid[0]) || grid[row][col] == 0 || visited[row][col] {
        return
    }
    // 记得要把当前单元格置为已访问，否则会重复访问
    visited[row][col] = true
    sum += grid[row][col]
    if sum > max {
        max = sum
    }
    // 上下左右四个方向都要照顾到
    backTrack(row-1, col, sum, grid, visited)
    backTrack(row+1, col, sum, grid, visited)
    backTrack(row, col-1, sum, grid, visited)
    backTrack(row, col+1, sum, grid, visited)
    visited[row][col] = false //回溯
}

179. 单词搜索 中等

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 1：
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出：true

示例 2：
输入：board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “SEE”
输出：true

提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成

题解概要：

1.使用剪枝和dfs要比回溯的效率更快。

代码：

func exist(board [][]byte, word string) bool {
    m := len(board)
    n := len(board[0])
    used := make([][]bool,m)
    for i,_ := range used{
        used[i] = make([]bool,n)
    }
    var dfs func(int,int,int)bool
    //r代表矩阵的行，c代表矩阵的列，i代表word下标
    dfs = func(r,c,i int)bool{
        //判断是否找到单词
        if i == len(word){
            return true
        }
        //判断是否越界
        if r < 0 || r >= m || c < 0 || c >= n{
            return false
        }
        //判断元素是否合规
        if used[r][c] || board[r][c] != word[i]{
            return false
        }
        //将元素标为已用过
        used[r][c] = true
        //继续搜索
        canFind := dfs(r+1,c,i+1) || dfs(r,c+1,i+1) || dfs(r-1,c,i+1) || dfs(r,c-1,i+1)
        //判断是否已搜索到结果
        if canFind{
            return true
        }else{
            used[r][c] = false
            return false
        }
    }
    for i := 0;i < m; i++{
        for j := 0;j < n;j++{
            if board[i][j] == word[0] && dfs(i,j,0){
                return true
            }
        }
    }
    return false
}

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

题解概要：

https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html#%E6%80%9D%E8%B7%AF

代码：

var ans [][]string
func solveNQueens(n int) [][]string {
    ans = [][]string{}
    //初始化棋盘
    chessboard := make([][]string,n)
    for i := 0;i < n;i++{
        chessboard[i] = make([]string,n)
        for j := 0;j < n;j++{
            chessboard[i][j] = "."
        }
    }
    backTracking(0,n,chessboard)
    return ans
}
func backTracking(row int,n int,chessboard [][]string){
    //满足条件
    if row == n{
        tmp := make([]string,n)
        for i := 0;i < n;i++{
            tmp[i] = strings.Join(chessboard[i],"")
        }
        ans = append(ans,tmp)
        return
    }
    for i := 0;i < n;i++{
        if isValid(row,i,n,chessboard){
            chessboard[row][i] = "Q"
            backTracking(row+1,n,chessboard)
            chessboard[row][i] = "."
        }
    }
}
func isValid(row int,col int,n int,chessboard [][]string)bool{
    //判断列上是否已放置皇后。
    for i := row-1;i >= 0;i--{
        if chessboard[i][col] == "Q"{
            return false
        }
    }
    //判断45°角上是否已放置皇后
    i := row-1
    j := col-1
    for i >= 0 && j >= 0{
        if chessboard[i][j] == "Q"{
            return false
        }
        i--
        j--
    }
    //判断135°角上是否已放置皇后
    i = row-1
    j = col+1
    for i >= 0 && j < n{
        if chessboard[i][j] == "Q"{
            return false
        }
        i--
        j++
    }
    return true
}

6. 其他

22. 括号生成 中等

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

示例 2：
输入：n = 1
输出：[“()”]

提示：

• 1 <= n <= 8

题解概要：

1.重要的是画出N叉树。

代码：

func generateParenthesis(n int) []string {
    ans := []string{}
    var backTracking func(int,int,[]byte)
    backTracking = func(left,right int,path []byte){
        //是否符合条件
        if len(path) == n*2{
            tmp := make([]byte,len(path))
            copy(tmp,path)
            ans = append(ans,string(tmp))
        }
        //添加左括号
        if left < n{
            path = append(path,'(')
            backTracking(left+1,right,path)
            path = path[:len(path)-1]
        }
        //添加右括号
        if left > right{
            path = append(path,')')
            backTracking(left,right+1,path)
            path = path[:len(path)-1]
        }
    }
    backTracking(0,0,[]byte{})
    return ans
}

131. 分割回文串 中等

给你一个字符串 s，请你将 _s _分割成一些子串，使每个子串都是回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。

示例 1：
输入：s = “aab”
输出：[[“a”,”a”,”b”],[“aa”,”b”]]

示例 2：
输入：s = “a”
输出：[[“a”]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

题解概要：

https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html#%E5%9B%9E%E6%BA%AF%E4%B8%89%E9%83%A8%E6%9B%B2

例如对于字符串abcdef：

• 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个…..。
• 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段…..。

所以切割问题，也可以抽象为一棵树形结构，如图：

代码：

func partition(s string) [][]string {
    ans := [][]string{}
    var backTracking func(int,[]string)
    backTracking = func(start int,path []string){
        if start >= len(s){
            tmp := make([]string,len(path))
            copy(tmp,path)
            ans = append(ans,tmp)
            return
        }
        for i := start;i < len(s);i++{
            //判断是否为回文串
            if !isValid(start,i,s){
                continue
            }
            path = append(path,s[start:i+1])
            backTracking(i+1,path)     //进入下一层
            path = path[:len(path)-1]
        }
    }
    backTracking(0,[]string{})
    return ans 
}
func isValid(l int,r int,s string)bool{
    for l < r{
        if s[l] != s[r]{
            return false
        }
        l ++
        r --
    }
    return true
}