LeetCode — Backtracking

The Backtracking Tips:

• Permutations. Problem 46. Problem 47. Problem 60. 526. 996.
• Combination problem Combination. Problem 39, 40, 77, 216.
• Permutation and combinatorial hybridization problems. The 1079th.
• N Queen ultimate solution (binary solution). Problem 51. Problem 52.
• Sudoku problem. 37 items.
• Search in four directions. Problem 79. Problem 212. Problem 980.
• Subset problem. Problem 78. Problem 90.
• Trie. Problem 208. Problem 211.
• BFS optimization. Problem 126. Problem 127.
• DFS template. (Just an example, not corresponding to any question)

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] { // Here is the key logic for deweighting
			continue
		}
		if target >= nums[i] {
			c = append(c, nums[i])
			findcombinationSum2(nums, target-nums[i], i+1, c, res)
			c = c[:len(c)- 1]}}}Copy the code

• BFS template. (Just an example, not corresponding to any question)

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
}
Copy the code