Recursive backtracking usually involves a recursive function and a loop inside the recursive function.
The N Queen problem, for example, every time it recurses, it goes to the next line and does some logic. In each row, each column is iterated over to determine whether the elements in the row and column meet the condition. Another example is the letter combination problem of telephone numbers. Each recursion leads to the next number, and then iterates through the list of letters corresponding to that number. Other problems are similar, but with some variation.
Since there are both recursion and loop structures, and recursion and loop follow these two structures, why not introduce recursion and loop lines?
Recursive lines can be thought of as linear structures for recursive traversal, such as N lines to be traversed in the N queen problem, N numbers to be traversed in the combination of letters of telephone numbers problem, a grid to be traversed in the word search problem, and an array of numbers to be traversed in the subset problem. The recursion point is the specific position of the recursion, such as a specific line in the queen of N, a specific number in the alphabet of a telephone number.
A loop is a number of possible options for a recursive point to traverse. For example, N columns need to be traversed in a line of N queen, a set of letters need to be traversed corresponding to a number in the letter combination of telephone numbers, and 4 neighboring grids need to be traversed in a grid of word search. And the cycle point is the specific position of the cycle, such as a specific row or column in the N Queen problem.
Recursion lines and loops complement each other. The point of a recursion selected during the loop is usually the next recursion point. For the word search problem, the selected cycle point is the recursion point for the next recursion, while for the n-queen problem, the choice of cycle point does not affect the next recursion point.
Retrospective recursion questions generally ask for a set. It is necessary to record the selected recursion points and cycle points during continuous recursion and cycle, and put the recursion points and cycle points recorded along the way into a set at an appropriate time. In general, a vector is used to record the selected loop point (push_back) for each recursion. On backtracking, the current loop point (pop_back) is cleared. Iterate to the next loop point and record it in vector.
Obviously, for a recursive backtracking problem, finding the recursion line and the loop line basically solves the problem. The code structure for these problems is similar: a recursive function + a for loop + a vector of position records.
Here are some exercises to grasp and reinforce this idea.
An explicit recursive loop
A combination of letters for a telephone number
Leetcode the original leetcode-cn.com/problems/le…
- Topic describes
Given a string containing only the numbers 2-9, return all the letter combinations it can represent. The answers can be returned in any order. The mapping of numbers to letters is given as follows (same as a telephone key). Note that 1 does not correspond to any letter.Copy the code
- example
Input: who = "23" output: [" AD ", "ae", "af", "bd", "be", "bf", "CD" and "ce", "cf"]Copy the code- Answer key
The number “23” can be used for recursive traversal. Each recursion accesses the next subscript number, that is, the number string itself is the recursion line, and each specific number is the recursion point. Each number has a pair of letters, and these letters are circular lines. When you get to a recursion point, you iterate over the letters on the loop. So:
- Recursive line:
Recursively iterates through each number in the string.
- Inner loop
Loop through an array of letters corresponding to the recursive point number.
- End conditions for recursion and inner loops
When all numbers are recursively traversed, the recursion is terminated. The loop is the letter of each number is traversed once, traversal can be terminated.
- Note:
Each recursion needs to record the value selected for the current loop.
- AC code
class Solution {
public:
vector<string> letterCombinations(string digits) {
m_vec.clear(a);if(digits.empty())
return m_vec;
std::string str;
dfs(digits, 0, str);
return m_vec;
}
void dfs(const std::string &digits, int index, std::string &str)
{
if(index == digits.size())
{
m_vec.push_back(str);
return ;
}
for(auto c : m_nums[digits[index]])// Loop over the letters corresponding to each number
{
str.push_back(c);// Record the loop value of this recursive selection
dfs(digits, index+1, str);
str.pop_back(a);// Release the loop for this recursive selection}}private:
std::vector<string> m_vec;
std::map<char, string> m_nums = { {'2'."abc"}, {'3'."def"}, {'4'."ghi"}, {'5'."jkl"}, {'6'."mno"}, {'7'."pqrs"}, {'8'."tuv"}, {'9'."wxyz"}}; };Copy the codeN queen
Leetcode the original leetcode-cn.com/problems/n-…
- Topic describes
The n Queens problem is the study of how to place n queens on an n by n board so that queens cannot attack each other. Given an integer n, return all the different solutions to the n queen problem. Each solution contains a different chess placement scheme for the N-queen problem, in which 'Q' and '.' represent queens and slots, respectively.Copy the code- example
Input: n = 4 output: [[". Q.. ", "... Q ", "Q...", ".. Q. "], [".. Q. ", "Q...", "... Q ", ". Q.. "]] : as shown in the above, 4 queen problems exist two different solutions.Copy the code- Answer key
In the n-queen problem, the recursion lines are the N rows on the board, and the loop lines at each recursion point are all the columns in that row. Because N queens cannot conflict with each other in the N queens problem, you need to check whether a column can be selected when iterating through it. This is also a slightly more complicated point, and I’m going to go through it and see if it satisfies this condition.
- Recursive line:
Recursively traverses each row of the board.
- Inner loop
Loop over N columns in a recursive row.
- End conditions for recursion and inner loops
The recursion terminates when none of the columns in the row satisfy the condition; The recursion terminates when it reaches the last row.
- Note:
During the cycle, we need to determine whether the cycle point meets the non-conflict condition of N queen.
- AC code
class Solution {
public:
vector<vector<string>> solveNQueens(int n) {
m_locations.clear(a); std::vector<int> locate;
dfs(locate, n);
std::vector<std::vector<std::string>> ret;
for(auto &vec : m_locations)
{
std::vector<std::string> vec_str(n, std::string(n, '. '));
for(int i = 0; i < vec.size(a); ++i) { vec_str[i][vec[i]] ='Q';
}
ret.push_back(std::move(vec_str));
}
return ret;
}
void dfs(std::vector<int> &locate, int n)
{
if(locate.size() == n)
{
m_locations.push_back(locate);
return ;
}
for(int i = 0; i < n; ++i)
{
if(isValid(locate, i))
{
locate.push_back(i);
dfs(locate, n);
locate.pop_back(a); }}}bool isValid(const std::vector<int> &locate, int index)
{
// The same column exists
if(std::find(locate.begin(), locate.end(), index) ! = locate.end())
return false;
// The difference of the oblique x axis is equal to the difference of the Y-axis on the oblique line
int size = locate.size(a);// This size is the y position of index
for(int i = 0; i < size; ++i)
{
int x_diff = std::abs(index - locate[i]);
int y_diff = size - i;
if(x_diff == y_diff)
return false;
}
return true;
}
private:
std::vector<std::vector<int>> m_locations;
};
Copy the codeWord search
Leetcode the original leetcode-cn.com/problems/wo…
- Topic describes
Given an M x N two-dimensional character grid board and a string word. Return true if Word exists in the grid; Otherwise, return false. Words must be formed in alphabetical order by letters in adjacent cells, where "adjacent" cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be reused.Copy the code- example
Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "ABCCED" output: trueCopy the code- Answer key
The recursion line is each cell, and the loop line of each recursion point is the four neighbors above, below, left and right of the cell. With recursion lines and loops, a skeleton code shelf emerges. There are a few other things to note. 1. The word doesn’t have to start on the upper-left grid, but on any grid. 2. Each grid needs to be walked only once, so it is necessary to record whether each grid has been walked; 3. The next recursive point of the edge cell cannot cross the boundary; 3. The selected cycle point is the recursion point for the next recursion.
- Recursive line:
Recursively traverses each cell in the grid.
- Inner loop
Iterate over the four neighbors of the recursive point grid. The loop needs to determine whether the cycle point has been passed.
- End conditions for recursion and inner loops
Terminates recursion when a cell does not match the next character of the word. The recursion terminates when you cross the boundary of the grid.
- Note:
As mentioned above
- AC code
class Solution {
public:
bool exist(vector<vector<char>>& board, string word) {
if(board.empty() || word.empty())
return false;
int row = board.size(a);int col = board[0].size(a);for(int i = 0; i < row; ++i)
{
for(int j = 0; j < col; ++j)
{
if(board[i][j] == word[0] && existCore(board, i, j , word, 0))
return true; }}return false;
}
bool existCore(std::vector<std::vector<char>> &mat, int i, int j, const std::string &word, int index)
{
if(mat[i][j] ! = word[index])return false;
else if(index+1 == word.size())
return true;
int row = mat.size(a);int col = mat[0].size(a);char record = The '#';
/ / to the left
if(j > 0)
{
std::swap(mat[i][j], record); // indicate that the grid has been passed
if(existCore(mat, i, j- 1, word, index+1))
return true;
std::swap(mat[i][j], record); // Undo the grid
}
/ / to the right
if(j < col- 1)
{
std::swap(mat[i][j], record);
if(existCore(mat, i, j+1, word, index+1))
return true;
std::swap(mat[i][j], record);
}
/ / down
if(i < row- 1 )
{
std::swap(mat[i][j], record);
if(existCore(mat, i+1, j, word, index+1))
return true;
std::swap(mat[i][j], record);
}
/ / up
if(i > 0 )
{
std::swap(mat[i][j], record);
if(existCore(mat, i- 1, j, word, index+1))
return true;
std::swap(mat[i][j], record);
}
return false; }};Copy the codeImplicit loop lines
Digital combination
Leetcode the original leetcode-cn.com/problems/co…
- Topic describes
Given two integers n and k, return all possible combinations of k numbers in the range [1, n]. You can return the answers in any order.Copy the code- example
Input: n = 4, k = 2 output: [[2, 4], [3, 4], [2, 3], [1, 2], [1, 3], [1, 4],]Copy the code- Answer key
In contrast to the previous problem, there is only one obvious recursive or circular line: n numbers from 1 to n. According to the experience of the previous problem, the array given by the problem is suitable as a recursive line. What’s the loop? Readers of these questions may know the answer: “Choose or not choose the current number.” For example, if you recurse to the number 3, you can either choose 3 or not choose 3. These two cases are circular lines. Of course, when there are only two cases, you don’t write it as a loop in your code. But the essence is a circular line.
- Recursive line:
Recursively iterate over each number in the array 1 through n
- Inner loop
Loop through the recursion point number selection and not selection of two cases.
- End conditions for recursion and inner loops
When the selected number reaches a preset k, the recursion terminates.
- Note:
Note pruning, when the number of unrecursed numbers left is less than k, there is no need to recurse. Because even if I picked all of them, I wouldn’t have enough k numbers.
- AC code
class Solution {
public:
vector<vector<int>> combine(int n, int k) {
m_collections.clear(a);std::vector<int> nums(n);
std::iota(nums.begin(), nums.end(), 1);
std::vector<int> vec;
dfs(nums, 0, vec, k);
return m_collections;
}
// veC stores the selected numbers, k indicates that there are still several numbers left to collect
void dfs(const std::vector<int> &nums, int index, std::vector<int> &vec, int k)
{
if(k == 0)
{
m_collections.push_back(vec);
return ;
}
/ / the pruning. K more numbers are needed, but there are not enough numbers available so far
if( (k > nums.size()-index) || index == nums.size()) {return ;
}
// Since there are only two cases, there is no need to write it as a loop
dfs(nums, index+1, vec, k); // Do not select this number
vec.push_back(nums[index]); // Select this number
dfs(nums, index+1, vec, k- 1);
vec.pop_back(a); }private:
std::vector<std::vector<int>> m_collections;
};
Copy the codeA subset of
Leetcode the original leetcode-cn.com/problems/su…
- Topic describes
You are given an array of integers, nums, whose elements are different from each other. Returns all possible subsets (power sets) of this array. The solution set cannot contain duplicate subsets. You can return the solution set in any order.Copy the code- example
Output: input: nums = [1, 2, 3], [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]Copy the code- Answer key
This problem is similar to the previous combination of numbers. The only difference is the recursive termination condition. The number combination is limited to k numbers. In this case, there is no such limitation.
- Recursive line:
Recursively iterate over each number in the array.
- Inner loop
There are two cases of traversing recursion point number selection and no selection.
- End conditions for recursion and inner loops
The recursion terminates when it reaches the last element of the array.
- Note:
No.
- AC code
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
m_vec.clear(a); std::vector<int> vec;
subSetsCore(nums, 0, vec);
return m_vec;
}
void subSetsCore(const std::vector<int> &nums, int startIndex, std::vector<int> &vec)
{
if(startIndex == nums.size())
{
m_vec.push_back(vec);
return ;
}
// Since there are only two cases, there is no need to write it as a loop
subSetsCore(nums, startIndex+1, vec);// Do not select this number
vec.push_back(nums[startIndex]);
subSetsCore(nums, startIndex+1, vec); // Select this number
vec.pop_back(a); }private:
std::vector<std::vector<int>> m_vec;
};
Copy the codeThe whole arrangement
Leetcode the original leetcode-cn.com/problems/pe…
- Topic describes
Given an array nums that does not contain duplicate digits, return all possible permutations. You can return the answers in any order.Copy the code- example
Output: input: nums = [1, 2, 3], [[1, 2, 3], [31] 1,,1,3 [2], [2,3,1], [3,1,2], [3, 2, 1]]Copy the code- Answer key
The recursion line for this problem is obvious, which is to iterate over each element of the array. What about the loop? Choose and not choose? It doesn’t satisfy the problem. Encountered this problem for the first time puzzled. After seeing the solution, Wocao can still play like this. For each recursion point the loop line is the recursion point element and the following element swap once. By constantly switching places in this way, different sorts are achieved.
- Recursive line:
Recursively iterates over each number in the pair array
- Inner loop
Loop over the element following the recursive point number and swap with the element at the recursive point.
- End conditions for recursion and inner loops
The recursion terminates when it reaches the last element of the array
- Note:
There is no
- AC code
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
m_ret.clear(a);dfs(nums, 0);
return m_ret;
}
void dfs(std::vector<int> &nums, int startIndex)
{
if(startIndex == nums.size())
{
m_ret.push_back(nums);
return ;
}
for(int i = startIndex; i < nums.size(a); ++i) { std::swap(nums[i], nums[startIndex]);
dfs(nums, startIndex+1);
std::swap(nums[i], nums[startIndex]); }}private:
vector<vector<int>> m_ret;
};
Copy the codeImplicit recursion and loop lines
Parentheses generates
Leetcode the original leetcode-cn.com/problems/ge…
- Topic describes
The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations. The combination of valid brackets must meet the following requirements: The left bracket must be closed in the correct sequenceCopy the code- example
Input: n = 3 output: [" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"]Copy the code- Answer key
It’s confusing at first, the recursion line and the loop line don’t have a clue. Create conditions when there are no conditions. Previous recursion lines recurse along a structure such as an array, a grid, etc. We don’t have any structure in this case. Can we recurse with the degree? So for example, the number of open parentheses you use, you recurse for every open parenthesis you use. It’s a good idea, but there are some details to be worked out. For example, in the example of a valid parenthesis combination ((())), how do I recurse three open parentheses followed by three close parentheses? Loop line?
Can we use parentheses as recursion lines? A loop is a recursion point that traverses [” select open parenthesis “, “select close parenthesis “]. So the cycle point that you choose is the recurrence point for the next recursion. This is similar to the previous word search question.
Also, like queen N, not all points on the loop line can be selected. You need to determine if this is a valid parenthesis order.
- Recursive line:
Pure recursion, no structural dependencies. Select a valid loop point on the loop line and then proceed to the next recursion as a recursive point.
- Inner loop
Loop through [” Select open parenthesis “, “select close parenthesis “]. The selection needs to check that the loop points are in a valid parenthesis order.
- End conditions for recursion and inner loops
When both parentheses are n, the traversal is terminated.
- Note:
There is no
- AC code
class Solution {
public:
vector<string> generateParenthesis(int n) {
m_vec.clear(a); std::string str;dfs(str, n, n);
return m_vec;
}
void dfs(std::string &str, int left_num, int right_num)
{
if(left_num == 0 && right_num == 0)
{
m_vec.push_back(str);
return ;
}
// We can continue with the open parenthesis
if(left_num > 0)
{
str.push_back('(');
dfs(str, left_num- 1, right_num);
str.pop_back(a); }// When the number of open parentheses in STR is greater than the number of close parentheses, we can continue to place a close parenthesis in STR.
if(left_num < right_num) // the < sign is the remainder
{
str.push_back(') ');
dfs(str, left_num, right_num- 1);
str.pop_back(a); }// Stop recursion naturally.
}
private:
std::vector<std::string> m_vec;
};
Copy the codeTo weight problems
Sum of combinations II
Leetcode the original leetcode-cn.com/problems/co…
- Topic describes
Given an array of candidates and a target number target, find all combinations of the candidates that can be the sum of the number and target. Each number in the candidates must be used only once in each combination. Note: The solution set cannot contain repeated combinationsCopy the code- example
Input: candidates =,1,2,7,6,1,5 [10], target = 8, output: [,1,6 [1],,2,5 [1], [1, 7], [2, 6]]Copy the code- Answer key
This problem is a variation of the previous problem “combination”, which is also a recursion through an array of integers to select a number. Only the recursive termination condition in this case contains the hypothesis that the sum of the selected numbers equals target.
Another point to note in this case is that the solution set cannot contain repeated combinations.
- Recursive line:
Recursively iterate over each number in the array.
- Inner loop
Loop through the recursion point number selection and not selection of two cases.
- End conditions for recursion and inner loops
The recursion terminates when it reaches the last element of the array; The traversal terminates when the sum of the selected numbers is greater than or equal to Target;
- Note:
To avoid duplicate combinations, refer to the code comments
- AC code
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
m_ret.clear(a);// Sort for reweighting
std::sort(candidates.begin(), candidates.end());
std::vector<int> path;
dfs(candidates, path, 0, target);
return m_ret;
}
void dfs(const std::vector<int> &candidates, std::vector<int> &path, int start_index, int target)
{
if(target == 0) // Meet the requirement
{
m_ret.push_back(path);
return ;
}
/ / the pruning
if(target < 0 || start_index >= candidates.size())
return ;
// Select this element
path.push_back(candidates[start_index]);
dfs(candidates, path, start_index+1, target-candidates[start_index]);
path.pop_back(a);// Unselect this element at start_index. You can't simply opt out. Consider [1, 2, 2, 2, 3, 4]
// Start_index is 1. For the previous selection, then the result set has [1, 2] if start_index is 1
// select 2 from start_index (1, 2); // select 2 from start_index (2)
// Therefore, if the value is skipped, the value is always skipped.
for(int v = candidates[start_index++]; start_index < candidates.size() && v == candidates[start_index]; )
++start_index;
dfs(candidates, path, start_index, target);
}
private:
std::vector<std::vector<int>> m_ret;
};
Copy the codeSubset II
Leetcode the original leetcode-cn.com/problems/su…
Problems involving repeated subsets
- Topic describes
Given an array of integers, nums, which may contain repeating elements, return all possible subsets (power sets) of that array. The solution set cannot contain duplicate subsets. Returns a solution set in which subsets can be arranged in any order.Copy the code- example
Output: input: nums =,2,2 [1], [[], [1], [1, 2],,2,2 [1], [2], [2]]Copy the code- Answer key
Recursion lines and loops are pretty straightforward, and recursion lines are arrays. The loop is the case of picking and not picking the recursive point number. It is important to avoid duplicate subsets. Skip the following elements with the same value.
Another point to note in this case is that the solution set cannot contain repeated combinations.
- Recursive line:
Recursively iterate over each number in the array.
- Inner loop
Loop through the recursion point number selection and not selection of two cases.
- End conditions for recursion and inner loops
The recursion terminates when it reaches the last element of the array;
- Note:
To avoid duplicate subsets, refer to the code comments
- AC code
class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
m_ret.clear(a); std::vector<int> vec;
std::sort(nums.begin(), nums.end());// Sort for reweighting
dfs(nums, vec, 0);
return m_ret;
}
void dfs(const std::vector<int> &nums, std::vector<int> &vec, int startIndex)
{
if(startIndex == nums.size())
{
m_ret.push_back(vec);
return ;
}
// Select the element
vec.push_back(nums[startIndex]);
dfs(nums, vec, startIndex+1);
vec.pop_back(a);// If this element is not selected, all the same elements need to be skipped
int val = nums[startIndex++];
while(startIndex < nums.size() && nums[startIndex] == val)
++startIndex;
dfs(nums, vec, startIndex);
}
private:
std::vector<std::vector<int>> m_ret;
};
Copy the codeThe whole arrangement II
Leetcode the original leetcode-cn.com/problems/pe…
- Topic describes
Given a sequence nums that can contain repeating digits, return all non-repeating full permutations in any order.Copy the code- example
Input: nums = [1,1,2] output: [[1,1,2], [2,1]]Copy the code- Answer key
This problem is the deformation of the front full arrangement, the difficulty is that there will be repeated numbers and need to be repeated. In the previous full permutation solution, it is necessary to swap the two digits in different positions, so even after sorting at the beginning, after recursion and various swaps, all possible permutations will exist (after all, the problem is full permutation). At this point can not simply use the previous method to remove the weight. The new deduplication method refers to comments in the code.
- Recursive line:
Recursively iterates over each number in the pair array
- Inner loop
Loop over the element following the recursive point number and swap with the element at the recursive point.
- End conditions for recursion and inner loops
The recursion terminates when it reaches the last element of the array
- Note:
Need to be de-duplicated, refer to the comments in the code
- AC code
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
m_ret.clear(a); std::sort(nums.begin(), nums.end());
dfs(nums, 0);
return m_ret;
}
void dfs(std::vector<int> &nums, int startIndex)
{
if(startIndex == nums.size())
{
m_ret.push_back(nums);
return ;
}
auto it = nums.begin(a);for(int i = startIndex; i < nums.size(a); ++i) {[startIndex, I] = nums[I] = nums[startIndex, I]
// Do a swap. Nums [I] = nums[startIndex] = nums[I] = startIndex
// Swap with I and startIndex to get the same array.
Nums [I] = nums[i-1] = nums[i-1] = nums[i-1
if(std::find(it+startIndex, it+i, nums[i]) == it+i) // there is no element with the same value as nums[I] between [startIndex, I]
{
std::swap(nums[i], nums[startIndex]);
dfs(nums, startIndex+1);
std::swap(nums[i], nums[startIndex]); }}}private:
std::vector<std::vector<int>> m_ret;
};
Copy the codeThe first time to receive the latest article, please pay attention to the same name wechat public number: Code color