回溯算法解题套路框架
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 46. Permutations | 🟠 |
| 51. N-Queens | 🔴 |
| 52. N-Queens II | 🔴 |
Prerequisites
Before reading this article, you need to learn:
Tip
本文有视频版：Backtracking Algorithm Framework Detailed Explanation。建议关注我的 B 站账号，我会用视频领读的方式带大家学习那些稍有难度的算法技巧。
This article is an advanced version of an earlier article Backtracking Algorithm Detailed Explanation. Once the framework is clear to you, you'll find that backtracking problems follow a similar pattern.
This article addresses several questions:
- What is a backtracking algorithm?
- What are the techniques to solve backtracking problems?
- How to learn backtracking algorithms?
- Is there a pattern to backtracking algorithm code?
In fact, backtracking algorithms can be considered almost the same as DFS (Depth-First Search) algorithms. The subtle differences are explained in detail in Several Questions About DFS and Backtracking Algorithms. This article focuses on backtracking algorithms without delving into those details.
Abstractly speaking, solving a backtracking problem is essentially the process of traversing a decision tree, where each leaf node contains a valid solution. By traversing the entire tree and collecting the solutions at the leaf nodes, you can obtain all valid solutions.
Standing at a node in the backtracking tree, you only need to consider 3 questions:
- Path: The choices you have already made.
- Choice List: The choices you can currently make.
- Termination Condition: The condition where you reach the bottom of the decision tree and can no longer make choices.
If you don't understand these terms, don't worry. We will use the classic backtracking problems "Permutations" and "N-Queens" to help you understand what these terms mean. For now, just keep them in mind.
Regarding the code, the framework for backtracking algorithms is:
result = []
def backtrack(path, choice_list):
if meets_termination_condition:
result.add(path)
return
for choice in choice_list:
make_choice
backtrack(path, choice_list)
undo_choiceThe core idea is to make choices before the recursive call and undo those choices after the recursive call within the for loop. It's quite simple.
What do we mean by making and undoing choices, and what is the underlying principle of this framework? Let's unravel these mysteries by exploring the "Permutations" problem in detail!
Permutations Problem
LeetCode problem #46 "Permutations" asks you to return all possible permutations of a given array nums.
Tip
In this discussion, we assume the permutations problem does not include duplicate numbers. The extended scenario with duplicate numbers will be covered in the later article Backtracking Algorithm to Master Permutations, Combinations, and Subsets.
Also, some readers might have seen permutation algorithms that use the swap method to exchange elements, which is different from the code introduced in this article. These are two exhaustive approaches in backtracking algorithms. I will clarify this in the later article Ball and Box Model: Two Perspectives on Backtracking Exhaustion. For now, just follow my approach.
We all did permutation and combination math problems in high school and know that there are n! permutations for n distinct numbers. How did we exhaustively list all permutations back then?
For example, given the numbers [1,2,3], you wouldn't list them randomly. Typically, you would:
First, fix the first position as 1, then the second position can be 2, making the third position 3; then change the second position to 3, making the third position 2; then change the first position to 2, and exhaust the last two positions...
This is essentially backtracking, something we intuitively used in high school. Some might even draw the following backtracking tree:
By traversing this tree from the root and recording the numbers on the path, you get all permutations. We can call this tree the "decision tree" of the backtracking algorithm.
Why is it called a decision tree? Because at each node, you are making a decision. For instance, if you are at the red node in the following diagram:
You have to decide whether to take the branch with 1 or the branch with 3. Why only 1 and 3? Because the branch with 2 is behind you, a choice you already made, and permutations do not allow repeating numbers.
Now we can clarify the terms from the beginning: [2] is the "path," recording your past choices; [1,3] is the "choice list," indicating your current options; the "termination condition" is reaching the bottom leaf nodes of the tree, which here means the choice list is empty.
If you understand these terms, you can consider the "path" and "choice" list as attributes of each node in the decision tree, as shown in the diagram with several blue nodes:
Our defined backtrack function acts like a pointer, moving through this tree while correctly maintaining the attributes of each node. Whenever it reaches a bottom leaf node, the "path" is a complete permutation.
Furthermore, how do you traverse a tree? This shouldn't be hard. Recall from the previous article Framework Thinking for Learning Data Structures that various search problems are essentially tree traversal problems. The traversal framework for a multi-way tree is as follows:
void traverse(TreeNode root) {
for (TreeNode child : root.childern) {
// operations needed at the preorder position
traverse(child);
// operations needed at the postorder position
}
}void traverse(TreeNode* root) {
for (TreeNode* child : root->childern) {
// operations needed at the preorder position
traverse(child);
// operations needed at the postorder position
}
}def traverse(root: TreeNode):
for child in root.children:
# operations needed at the preorder position
traverse(child)
# operations needed at the postorder positionfunc traverse(root *TreeNode) {
for _, child := range root.children {
// operations needed at the preorder position
traverse(child)
// operations needed at the postorder position
}
}var traverse = function(root) {
for (var i = 0; i < root.children.length; i++) {
// operations needed at the preorder position
traverse(root.children[i]);
// operations needed at the postorder position
}
}相关信息
Careful readers might wonder: shouldn't the pre-order and post-order positions in the multi-way tree DFS traversal framework be outside the for loop, not inside it? Why are they inside the for loop in backtracking algorithms?
Yes, the pre-order and post-order positions in DFS algorithms should be outside the for loop. However, backtracking algorithms are slightly different from DFS algorithms. The detailed comparison will be discussed in the later section Graph Theory Basics, so you can ignore this issue for now.
The so-called pre-order and post-order traversals are just two very useful time points. Let me draw a picture to illustrate:
Pre-order traversal code is executed at the time point before entering a node, and post-order traversal code is executed at the time point after leaving a node.
Recall what we mentioned earlier: "path" and "choice" are attributes of each node. The function needs to correctly handle these attributes as it traverses the tree, so actions need to be taken at these two special time points:
Now, do you understand this core framework of the backtracking algorithm?
for choice in choice_list:
# make a choice
remove the choice from the choice list
path.add(choice)
backtrack(path, choice_list)
# undo the choice
path.remove(choice)
add the choice back to the choice listBy making a choice before the recursive call and undoing that choice after the recursive call, we can correctly obtain the choice list and path for each node.
Next, let's directly look at the code for generating all permutations:
class Solution {
List<List<Integer>> res = new LinkedList<>();
// main function, input a set of non-repeating numbers, return all permutations
List<List<Integer>> permute(int[] nums) {
// record the "path"
LinkedList<Integer> track = new LinkedList<>();
// elements in the "path" are marked as true to avoid reuse
boolean[] used = new boolean[nums.length];
backtrack(nums, track, used);
return res;
}
// path: recorded in track
// choice list: elements not in track in nums (used[i] is false)
// end condition: all elements in nums have appeared in track
void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used) {
// trigger the end condition
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
for (int i = 0; i < nums.length; i++) {
// exclude illegal choices
if (used[i]) {
// nums[i] is already in track, skip
continue;
}
// make a choice
track.add(nums[i]);
used[i] = true;
// go to the next level of decision tree
backtrack(nums, track, used);
// cancel the choice
track.removeLast();
used[i] = false;
}
}
}class Solution {
private:
vector<vector<int>> res;
public:
// main function, input a set of non-repeating numbers, return all permutations
vector<vector<int>> permute(vector<int>& nums) {
// record the "path"
vector<int> track;
// elements in the "path" are marked as true to avoid reuse
vector<bool> used(nums.size(), false);
backtrack(nums, track, used);
return res;
}
// path: recorded in track
// choice list: elements not in track in nums
// end condition: all elements in nums have appeared in track
void backtrack(vector<int>& nums, vector<int>& track, vector<bool>& used) {
// trigger the end condition
if (track.size() == nums.size()) {
res.push_back(track);
return;
}
for (int i = 0; i < nums.size(); i++) {
// exclude illegal choices
if (used[i]) {
// nums[i] is already in track, skip
continue;
}
// make a choice
track.push_back(nums[i]);
used[i] = true;
// enter the next level of decision tree
backtrack(nums, track, used);
// cancel the choice
track.pop_back();
used[i] = false;
}
}
};from typing import List
class Solution:
def __init__(self):
self.res = []
# main function, input a group of non-repeating numbers, return all permutations
def permute(self, nums: List[int]) -> List[List[int]]:
# record the "path"
track = []
# elements in the "path" are marked as true to avoid reuse
used = [False] * len(nums)
self.backtrack(nums, track, used)
return self.res
# path: recorded in track
# choice list: elements not in track in nums (used[i] is false)
# end condition: all elements in nums are present in track
def backtrack(self, nums: List[int], track: List[int], used: List[bool]):
# trigger end condition
if len(track) == len(nums):
self.res.append(track.copy())
return
for i in range(len(nums)):
# exclude invalid choices
if used[i]:
# nums[i] is already in track, skip
continue
# make a choice
track.append(nums[i])
used[i] = True
# enter the next level of decision tree
self.backtrack(nums, track, used)
# cancel the choice
track.pop()
used[i] = Falsefunc permute(nums []int) [][]int {
res := [][]int{}
track := []int{}
used := make([]bool, len(nums))
backtrack(nums, track, used, &res)
return res
}
// path: recorded in track
// choice list: elements in nums that are not in track
// termination condition: all elements in nums have appeared in track
func backtrack(nums []int, track []int, used []bool, res *[][]int) {
// trigger the termination condition
if len(track) == len(nums) {
// since track is a global variable, a new array needs to be created to store a permutation
temp := make([]int, len(track))
copy(temp, track)
*res = append(*res, temp)
return
}
for i := range nums {
// exclude illegal choices
if used[i] {
// pruning to avoid reusing the same number
continue
}
// make a choice
track = append(track, nums[i])
used[i] = true
// go to the next level of the decision tree
backtrack(nums, track, used, res)
// cancel the choice
track = track[:len(track)-1]
used[i] = false
}
}var permute = function(nums) {
let res = [];
let track = [];
let used = new Array(nums.length).fill(false);
// path: recorded in track
// choice list: elements in nums that are not in track
// end condition: all elements in nums have appeared in track
const backtrack = (nums, track, used) => {
// trigger the end condition
if (track.length === nums.length) {
res.push(track.slice());
return;
}
for (let i = 0; i < nums.length; i++) {
// exclude illegal choices
if (used[i]) {
// pruning to avoid using the same number repeatedly
continue;
}
// make a choice
track.push(nums[i]);
used[i] = true;
// go to the next level of the decision tree
backtrack(nums, track, used);
// cancel the choice
track.pop();
used[i] = false;
}
}
backtrack(nums, track, used);
return res;
};We've made a slight modification here. Instead of explicitly recording the "selection list," we use a used array to exclude elements that already exist in track, thereby deducing the current selection list:
With this, we have explained the underlying principles of the backtracking algorithm through the permutation problem. Of course, this algorithm is not the most efficient for generating permutations. You might see solutions that don't even use a used array, achieving the goal through element swapping. However, those methods are a bit harder to understand, so we won't cover them here. If you're interested, you can search for them on your own.
It's important to note that no matter how you optimize, it will still fit within the backtracking framework, and the time complexity cannot be lower than O(N!), because exhaustively traversing the entire decision tree is unavoidable. You will ultimately need to enumerate N! permutations. This is a characteristic of backtracking algorithms: unlike dynamic programming, which can optimize overlapping subproblems, backtracking is purely brute-force enumeration, and the complexity is generally high.
Once you understand the permutation problem, you can directly apply the backtracking algorithm framework. Let's briefly look at the N-Queens problem next.
II. N-Queens Problem
LeetCode problem #51, "N-Queens," is a classic example. Here's a simple explanation: you are given an N×N chessboard and asked to place N queens such that they cannot attack each other. Your task is to calculate all possible arrangements. The function signature is as follows:
List<List<String>> solveNQueens(int n);vector<vector<string>> solveNQueens(int n);def solveNQueens(n: int) -> List[List[str]]:func solveNQueens(n int) [][]string {
}var solveNQueens = function(n) {
// Code
};提示
A queen can attack any unit in the same row, the same column, and the four diagonal directions (top-left, bottom-left, top-right, bottom-right).
For example, if you are given N = 4, you need to place 4 queens on a 4x4 chessboard, returning the following results (using . to represent an empty space and Q to represent a queen):
[
[".Q..","...Q","Q...","..Q."],
["..Q.","Q...","...Q",".Q.."]
]
This problem is essentially similar to the permutation problem. Each level of the decision tree represents each row on the chessboard; the choice each node can make is to place a queen in any column of that row. Directly apply the backtracking algorithm framework:
public class Solution {
private List<List<String>> res = new ArrayList<>();
// input the length of the chessboard n, return all valid placements
public List<List<String>> solveNQueens(int n) {
// each string represents a row, and the list of strings represents a chessboard
// '.' means empty, 'Q' means queen, initialize an empty chessboard
List<String> board = new ArrayList<>();
for (int i = 0; i < n; i++) {
board.add(".".repeat(n));
}
backtrack(board, 0);
return res;
}
// path: those rows in board that `index < row` have successfully placed the queens
// choice list: all columns in the row are choices to place the queen
// end condition: row exceeds the last row of the board
private void backtrack(List<String> board, int row) {
// trigger the end condition
if (row == board.size()) {
res.add(new ArrayList<>(board));
return;
}
int n = board.get(row).length();
for (int col = 0; col < n; col++) {
// exclude illegal choices
if (!isValid(board, row, col)) {
continue;
}
// make a choice
char[] rowChars = board.get(row).toCharArray();
rowChars[col] = 'Q';
board.set(row, new String(rowChars));
// move to the next row decision
backtrack(board, row + 1);
// cancel the choice
rowChars[col] = '.';
board.set(row, new String(rowChars));
}
}
// can a queen be placed at board[row][col]?
private boolean isValid(List<String> board, int row, int col) {
int n = board.size();
// check if there are queens in the same column conflicting
for (int i = 0; i <= row; i++) {
if (board.get(i).charAt(col) == 'Q') {
return false;
}
}
// check if there are queens in the upper right conflicting
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
// check if there are queens in the upper left conflicting
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board.get(i).charAt(j) == 'Q') {
return false;
}
}
return true;
}
}class Solution {
private:
vector<vector<string>> res;
public:
// Input the length of the chessboard n, return all valid placements
vector<vector<string>> solveNQueens(int n) {
// Each string represents a row, and the list of strings represents a chessboard
// '.' means empty, 'Q' means queen, initialize an empty chessboard
vector<string> board(n, string(n, '.'));
backtrack(board, 0);
return res;
}
// Path: those rows in board that are less than row have successfully placed queens
// Choice list: all columns in the row are choices to place the queen
// End condition: row exceeds the last row of the board
void backtrack(vector<string>& board, int row) {
// Trigger the end condition
if (row == board.size()) {
res.push_back(board);
return;
}
int n = board[row].size();
for (int col = 0; col < n; col++) {
// Exclude invalid choices
if (!isValid(board, row, col)) {
continue;
}
// Make a choice
board[row][col] = 'Q';
// Move to the next row decision
backtrack(board, row + 1);
// Undo the choice
board[row][col] = '.';
}
}
// Can a queen be placed at board[row][col]?
bool isValid(vector<string>& board, int row, int col) {
int n = board.size();
// Check if there are queens conflicting in the column
for (int i = 0; i <= row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// Check if there are queens conflicting in the upper right
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
// Check if there are queens conflicting in the upper left
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}
};class Solution:
def __init__(self):
self.res = []
# Input the length of the chessboard n, return all valid placements
def solveNQueens(self, n: int) -> List[List[str]]:
# Each string represents a row, the list of strings represents a chessboard
# '.' represents empty, 'Q' represents a queen, initialize an empty chessboard
board = ["." * n for _ in range(n)]
self.backtrack(board, 0)
return self.res
# Path: those rows in board that are less than row have successfully placed queens
# Choice list: all columns of the row are choices to place the queen
# End condition: row exceeds the last row of the board
def backtrack(self, board, row):
# Trigger the end condition
if row == len(board):
self.res.append(board.copy())
return
n = len(board[row])
for col in range(n):
# Exclude invalid choices
if not self.isValid(board, row, col):
continue
# Make a choice
board[row] = board[row][:col] + 'Q' + board[row][col+1:]
# Move to the next row decision
self.backtrack(board, row + 1)
# Undo the choice
board[row] = board[row][:col] + '.' + board[row][col+1:]
# Can a queen be placed at board[row][col]?
def isValid(self, board, row, col):
n = len(board)
# Check if there is a conflict of queens in the column
for i in range(0, row+1):
if board[i][col] == 'Q':
return False
# Check if there is a conflict of queens in the upper right
for i, j in zip(range(row - 1, -1, -1), range(col + 1, n)):
if board[i][j] == 'Q':
return False
# Check if there is a conflict of queens in the upper left
for i, j in zip(range(row - 1, -1, -1), range(col - 1, -1, -1)):
if board[i][j] == 'Q':
return False
return Trueimport (
"strings"
)
// Input the length of the chessboard n, return all valid placements
func solveNQueens(n int) [][]string {
// Each string represents a row, and the list of strings represents a chessboard
// '.' represents an empty space, 'Q' represents a queen, initialize an empty chessboard
var board []string
var res [][]string
for i := 0; i < n; i++ {
board = append(board, strings.Repeat(".", n))
}
var backtrack func(board []string, row int)
backtrack = func(board []string, row int) {
// Trigger the end condition
if row == len(board) {
temp := make([]string, len(board))
copy(temp, board)
res = append(res, temp)
return
}
for col := 0; col < n; col++ {
// Exclude invalid choices
if !isValid(board, row, col) {
continue
}
// Make a choice
rowChars := []rune(board[row])
rowChars[col] = 'Q'
board[row] = string(rowChars)
// Move to the next row for decision
backtrack(board, row+1)
// Cancel the choice
rowChars[col] = '.'
board[row] = string(rowChars)
}
}
backtrack(board, 0)
return res
}
// isValid checks if a queen can be placed at board[row][col]?
func isValid(board []string, row, col int) bool {
n := len(board)
// Check if there is a conflict of queens in the column
for i := 0; i <= row; i++ {
if board[i][col] == 'Q' {
return false
}
}
// Check if there is a conflict of queens in the upper right
for i, j := row-1, col+1; i >= 0 && j < n; i, j = i-1, j+1 {
if board[i][j] == 'Q' {
return false
}
}
// Check if there is a conflict of queens in the upper left
for i, j := row-1, col-1; i >= 0 && j >= 0; i, j = i-1, j-1 {
if board[i][j] == 'Q' {
return false
}
}
return true
}var solveNQueens = function(n) {
let res = [];
// each string represents a row, and the list of strings represents a chessboard
// '.' represents empty, 'Q' represents the queen, initialize an empty chessboard
let board = new Array(n).fill(".").map(() => new Array(n).fill(".").join(""));
backtrack(res, board, 0);
return res;
}
// path: those rows in board that are less than row have successfully placed the queen
// choice list: all columns of the row are choices to place the queen
// termination condition: row exceeds the last row of the board
function backtrack(res, board, row) {
// trigger the termination condition
if (row == board.length) {
res.push(board.map(arr => arr.slice()));
return;
}
let n = board[row].length;
for (let col = 0; col < n; col++) {
// exclude illegal choices
if (!isValid(board, row, col)) {
continue;
}
// make a choice
let rowChars = board[row].split('');
rowChars[col] = 'Q';
board[row] = rowChars.join('');
// move to the next row decision
backtrack(res, board, row + 1);
// undo the choice
rowChars[col] = '.';
board[row] = rowChars.join('');
}
}
// can a queen be placed at board[row][col]?
function isValid(board, row, col) {
let n = board.length;
// check if there are queens in the column that conflict with each other
for (let i = 0; i <= row; i++) {
if (board[i][col] == 'Q') {
return false;
}
}
// check if there are queens in the upper right that conflict with each other
for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (board[i][j] == 'Q') {
return false;
}
}
// check if there are queens in the upper left that conflict with each other
for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (board[i][j] == 'Q') {
return false;
}
}
return true;
}相关信息
Some readers might wonder, according to the description of the N-Queens problem, why do we only check the top-left, top-right, and above squares, and not the bottom-left, bottom-right, and below squares?
This is because queens are placed row by row from top to bottom, so we don't need to check the bottom-left, bottom-right, and directly below squares (as no queens have been placed there yet). Since only one queen is placed per row, we don't need to check each row. In the end, we only need to check the top, top-left, and top-right directions.
The function backtrack still acts like a pointer wandering through a decision tree. Using row and col, it represents the position the function has traversed to. The isValid function prunes cases that do not meet the conditions:
If you were given such a large chunk of solution code, you might feel confused. But now that you understand the framework of the backtracking algorithm, what's difficult to comprehend? It's just a matter of modifying the way choices are made and excluding invalid choices. As long as you have the framework in mind, you're left with only minor issues.
When N = 8, it becomes the Eight Queens problem. The great mathematician Gauss spent his entire life trying to count all the possible arrangements for the Eight Queens problem, but our algorithm can calculate all possible results in just one second.
However, it's not really Gauss's fault. The complexity of this problem is indeed very high. A rough estimate:
In an N-row chessboard, the first row has N possible positions for a queen, the second row has N - 1 positions, the third row has N - 2 positions, and so on. Adding the O(N) complexity required by the isValid function before placing each queen, the total time complexity upper bound is O(N! * N), and there are no obvious redundant calculations to optimize efficiency. You can try N = 10, and you'll find the computation quite time-consuming.
Of course, due to the pruning by the isValid function, it won't actually try placing a queen in every position, so the actual execution efficiency will be higher. But as mentioned in the previous article A Practical Guide to Algorithm Time and Space Complexity Analysis, this time complexity as an upper bound is acceptable.
Sometimes, if we don't want to find all valid solutions and only need one solution, what should we do? For example, in a Sudoku solving algorithm, finding all solutions is too complex, and finding just one solution is sufficient.
It's actually quite simple. Just slightly modify the backtracking algorithm code to use an external variable to record whether a solution has been found. Once a solution is found, stop the recursive process:
boolean found = false;
// the function returns true after finding one answer
void backtrack(List<String> board, int row) {
if (found) {
// already found one answer, no need to search further
return;
}
// trigger the termination condition
if (row == board.size()) {
res.add(board);
// found the first answer
found = true;
return;
}
...
}bool found = false;
// the function returns true after finding one answer
void backtrack(vector<string>& board, int row) {
if (found) {
// already found one answer, no need to continue searching
return;
}
// trigger the termination condition
if (row == board.size()) {
res.push_back(board);
// found the first answer
found = true;
return;
}
// ...
}```python
found = False
# the function returns true after finding one solution
def backtrack(board: [str], row: int) -> None:
global found
if found:
# already found a solution, no need to keep looking
return
# trigger the termination condition
if row == len(board):
res.append(board)
# found the first solution
found = True
return
...var found bool = false
// the function returns true after finding one solution
func backtrack(board []string, row int) {
if found {
// already found a solution, no need to search further
return
}
// trigger the termination condition
if row == len(board) {
res = append(res, board)
// found the first solution
found = true
return
}
// ...
}var found = false;
// the function returns true after finding one answer
var backtrack = function(board, row) {
if (found) {
// already found one answer, no need to search anymore
return;
}
// trigger the termination condition
if (row == board.size) {
res.push(board);
// found the first answer
found = true;
return;
}
// ...
}With this modification, once a solution is found, subsequent recursive exhaustive searches will be halted. Perhaps you can slightly modify the code framework of the N-Queens problem to write a Sudoku-solving algorithm? You can refer to my article Backtracking Algorithm to Solve Sudoku for guidance.
Let's briefly expand on this. Sometimes, the problem might not require you to calculate all the specific solutions to the N-Queens problem, but simply ask for the total number of solutions. How would you approach this?
For example, LeetCode problem #52 "N-Queens II":
Given an integer n, return the number of distinct solutions to the N-Queens problem. For instance, if the input is n = 4, your algorithm should return 2, as there are only two feasible solutions for a 4x4 chessboard.
Actually, you can also solve this problem by copying the solution we wrote earlier, because the res variable we calculated stores all valid chessboards. Therefore, the number of elements in res is the total number of feasible solutions, right?
That's correct, but keep in mind that creating and storing these specific chessboard solutions consumes space and time, so the efficiency might be somewhat lower.
A better approach is to directly change the res variable to an int type and increment it each time a valid solution is found at the base case:
// simply record the count of valid results
int res = 0;
void backtrack(List<String> board, int row) {
if (row == board.size()) {
// found a valid result
res++;
return;
}
// the rest are all the same
}// simply record the number of valid results
int res = 0;
void backtrack(vector<string>& board, int row) {
if (row == board.size()) {
// found a valid result
res++;
return;
}
// the rest are all the same
}# Just record the number of valid results
res = 0
def backtrack(board, row):
global res
# When the number of rows is consistent with the size of the board, a valid result is found
if row == len(board):
# Found a valid result
res += 1
return
# The rest are all the same// Just record the number of valid results
var res int = 0
func backtrack(board []string, row int) {
if row == len(board) {
// Found a valid result
res++
return
}
// The rest are all the same
}// Just record the number of valid results
var res = 0;
var backtrack = function(board, row) {
// When should we record the result?
if (row == board.length) {
// Found a valid result
res++;
return;
}
// The rest are the same
}III. Final Summary
Backtracking algorithm is essentially a traversal problem of a multi-way tree. The key is to perform some operations at the positions of pre-order and post-order traversal. The algorithm framework is as follows:
def backtrack(...):
for choice in choice_list:
make_choice
backtrack(...)
undo_choiceWhen writing the backtrack function, you need to maintain the "path" you have taken and the current "choice list". When the "termination condition" is triggered, add the "path" to the result set.
Actually, if you think about it, isn't backtracking a bit similar to dynamic programming? In our series of articles on dynamic programming, we repeatedly emphasized that the three points that need to be clear in dynamic programming are "state", "choice", and "base case". Don't these correspond to the "path" taken, the current "choice list", and the "termination condition"?
Both dynamic programming and backtracking abstract the problem into a tree structure at a low level, but these two algorithms are completely different in their approaches. In Dong's Guide to Binary Trees (Outline), you will see a deeper distinction and connection between dynamic programming and backtracking algorithms.
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路：
