2.08 ✅ Quay lui (Backtracking)

Các dạng bài toán:

• Hoán vị (Permutations): Bài 46, 47, 60, 526, 996
• Tổ hợp (Combination): Bài 39, 40, 77, 216
• Bài toán lai giữa hoán vị và tổ hợp: Bài 1079
• N-Queens – lời giải tối ưu (dùng bit): Bài 51, 52
• Sudoku: Bài 37
• Tìm kiếm 4 hướng: Bài 79, 212, 980
• Tập con (Subsets): Bài 78, 90
• Trie: Bài 208, 211
• Tối ưu BFS: Bài 126, 127
• Mẫu DFS: (chỉ là ví dụ, không gắn với bài cụ thể nào)

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] {  // Đây là logic then chốt để loại bỏ trùng lặp
			continue
		}
		if target >= nums[i] {
			c = append(c, nums[i])
			findcombinationSum2(nums, target-nums[i], i+1, c, res)
			c = c[:len(c)-1]
		}
	}
}

• Mẫu BFS: (chỉ là ví dụ minh họa, không tương ứng với bài cụ thể nào)

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
}

---