LeetCode 分类刷题 —— Backtracking

Backtracking 的 Tips:

• 排列问题 Permutations。第 46 题，第 47 题。第 60 题，第 526 题，第 996 题。
• 组合问题 Combination。第 39 题，第 40 题，第 77 题，第 216 题。
• 排列和组合杂交问题。第 1079 题。
• N 皇后终极解法(二进制解法)。第 51 题，第 52 题。
• 数独问题。第 37 题。
• 四个方向搜索。第 79 题，第 212 题，第 980 题。
• 子集合问题。第 78 题，第 90 题。
• Trie。第 208 题，第 211 题。
• BFS 优化。第 126 题，第 127 题。
• DFS 模板。(只是一个例子，不对应任何题)

func combinationSum2(candidates []int, target int) [][]int {
    if len(candidates) == 0 {
        return [][]int{}
    }
    c, res := []int{}, [][]int{}
    sort.Ints(candidates)
    findcombinationSum2(candidates, target, 0, c, &res)
    return res
}

func findcombinationSum2(nums []int, target, index int, c []int, res *[][]int) {
    if target == 0 {
        b := make([]int, len(c))
        copy(b, c)
        *res = append(*res, b)
        return
    }
    for i := index; i < len(nums); i++ {
        if i > index && nums[i] == nums[i-1] { // 这里是去重的关键逻辑
            continue
        }
        if target >= nums[i] {
            c = append(c, nums[i])
            findcombinationSum2(nums, target-nums[i], i+1, c, res)
            c = c[:len(c)-1]
        }
    }
}

• BFS 模板。(只是一个例子，不对应任何题)

func updateMatrix_BFS(matrix [][]int) [][]int {
    res := make([][]int, len(matrix))
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return res
    }
    queue := make([][]int, 0)
    for i, _ := range matrix {
        res[i] = make([]int, len(matrix[0]))
        for j, _ := range res[i] {
            if matrix[i][j] == 0 {
                res[i][j] = -1
                queue = append(queue, []int{i, j})
            }
        }
    }
    level := 1
    for len(queue) > 0 {
        size := len(queue)
        for size > 0 {
            size -= 1
            node := queue[0]
            queue = queue[1:]
            i, j := node[0], node[1]
            for _, direction := range [][]int{{-1, 0}, {1, 0}, {0, 1}, {0, -1}} {
                x := i + direction[0]
                y := j + direction[1]
                if x < 0 || x >= len(matrix) || y < 0 || y >= len(matrix[0]) || res[x][y] < 0 || res[x][y] > 0 {
                    continue
                }
                res[x][y] = level
                queue = append(queue, []int{x, y})
            }
        }
        level++
    }
    for i, row := range res {
        for j, cell := range row {
            if cell == -1 {
                res[i][j] = 0
            }
        }
    }
    return res
}