Without further ado, just shout a slogan to encourage yourself: Programmers will never be unemployed, programmers go to architecture! The theme of this blog is [Backtracking Algorithm], which is implemented using the basic data structure [array]. The website for this high-frequency question is: CodeTop, and the filtering conditions are: Target company + Last year + Sort by frequency of appearance, from high to low, go to Niuke TOP101 to find it, it only appears in two places Before doing this question (CodeTop itself gathers the sources of LeetCode), make sure that the questions you answer are all frequently asked in interviews.
After clarifying the target question, attach the link to the question. Later, you can practice quickly and repeatedly based on the problem-solving ideas.The questions are classified according to the basic data structure of the question stem, and the first article in each category must be Is an introduction to basic data structures.
Full arrangement【MID】
A high-frequency problem that I have always wanted to solve, understand the backtracking algorithm, and solve the classic problem of the backtracking algorithm: full arrangement, the arrangement tree is as follows
Question stem
Problem-solving ideas
Address of the solution to the original problem We have done math problems of permutation and combination in high school. We also know that there are n non-repeating numbers, and there are n! in total permutation. So how did we exhaustively arrange them all? For example, given three numbers [1,2,3], the general process is as follows: first fix the first digit to 1, then the second digit can be 2, then the third digit can only be 3; then you can change the second digit to becomes 3, the third digit can only be 2; then the first digit can only be changed to 2, and then the last two digits can be exhausted
Just traverse the tree from the root and record the numbers on the path, which is actually the complete arrangement. We might as well call this tree the “Decision Tree” of the backtracking algorithm. Why do you say this is a decision tree? Because you are actually making decisions at each node. For example, let’s say you are standing on the red node in the picture below
You are making a decision now. You can choose the branch 1 or the branch 3. Why can I only choose between 1 and 3? Because the branch 2 is behind you, you have made this choice before, and full arrangement does not allow repeated use of numbers. So [2] is the “path”, which records the choices you have made; [1,3] is the “selection list”, which represents the choices you can currently make; the “end condition” is to traverse to the bottom of the tree Leaf node, here is when the selection list is empty
The backtrack function we defined is actually like a pointer, walking around the tree, and at the same time correctly maintaining the attributes of each node. Whenever it reaches the bottom leaf node of the tree, its “path” is a full arrangement,“Path” and “Selection” are attributes of each node. To correctly handle the attributes of nodes when the function travels on the tree, some actions must be taken at these two special points in time
So its core logic is
for selection in selection list:
# make decisions
Remove this selection from the selection list
path.add(select)
backtrack(path, selectlist)
# Unselect
path.remove(select)
Add this selection to the selection list
It conforms to the backtracking framework, and the time complexity cannot be lower than O(N!), because it is unavoidable to exhaustively enumerate the entire decision tree, and you will definitely have to exhaustively enumerate N! kinds of all-permutation results. This is also a characteristic of the backtracking algorithm. Unlike dynamic programming, which has overlapping sub-problems that can be optimized, the backtracking algorithm is purely brute force and is generally very complex.
Code implementation
Give the code to implement the basic file
Basic data structure: Array
Auxiliary data structure: None
Algorithm: Backtracking Algorithm
Tips: None
import java.util.*;
public class Solution {<!-- -->
//Define result set parameters
private ArrayList<ArrayList<Integer>> result = new
ArrayList<ArrayList<Integer>>();
// define path
ArrayList<Integer> path = new ArrayList<Integer>();
/**
* The class name, method name, and parameter name in the code have been specified. Please do not modify them. Just return the value specified by the method.
*
*
* @param num int integer one-dimensional array
* @return int integer ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> permute (int[] num) {<!-- -->
// 1 storage usage identifier
boolean[] used = new boolean[num.length];
// 2 Backtrack to find the path storage path, num is the selection list
backTrack(num, used);
return result;
}
private void backTrack(int[] num, boolean[] used) {<!-- -->
// 1 Set the end condition, find the leaf nodes, and supplement the result set
if (path.size() == num.length) {<!-- -->
result.add(new ArrayList<Integer>(path));
return;
}
// 2 Traverse the selection list and add elements in the selection list to the path list
for (int i = 0; i < num.length; i + + ) {<!-- -->
// 1 The element that has been used is illegal, jump out of the loop
if (used[i] == true) {<!-- -->
continue;
}
// 2 Take the current element out of the selection list and put it into the path list
used[i] = true;
path.add(num[i]);
// 3 Go to the next level of selection
backTrack(num, used);
// 4 Backtrack, put the current element back into the selection list, and remove it from the path list
used[i] = false;
path.remove(path.size() - 1);
}
}
}
Complexity analysis
The above code is a backtracking algorithm used to generate a full array of integer arrays. The following is an analysis of its time complexity and space complexity:
Time complexity:
-
The time complexity of a backtracking algorithm usually depends on the depth of the recursion and the number of operations per level of recursion. In this algorithm, each level of recursion tries each element in the
numarray until the termination condition is reached. -
At each level of recursion, there is a loop that iterates over all elements of the
numarray. Since each element is considered once, there arenelements in total, so there areO(n)operations at each level of recursion. -
The depth of the recursion depends on the size of the
numarray, which isn. In the worst case, the recursion goesnlevels deep, so the total time complexity isO(n * n!).
Space complexity:
-
The space complexity mainly depends on the depth of the recursive call and the data structure used to store the intermediate results.
-
The depth of recursion is
n, so there will be at mostnlevels of recursion frames in the call stack. Each recursive frame includes ausedarray and apatharray, both of which have space complexity ofO(n). -
Since there are
nlevels of recursive frames, the total space complexity isO(n^2).
To sum up, the time complexity of the above code is O(n * n!), where n is the size of the input array num, The space complexity is O(n^2). Due to the nature of the total permutation problem, this time complexity is acceptable, because the number of total permutations itself is n!, so the algorithm that generates all permutations must have factorial time complexity.
Full Arrangement II
To increase the difficulty, select all combinations in a selection list with repeated elements
Question stem
Problem-solving ideas
Assuming that the input is nums = [1,2,2'], the standard full permutation algorithm will give the following answer:
[
[1,2,2'],[1,2',2],
[2,1,2'],[2,2',1],
[2',1,2],[2',2,1]
]
Obviously, there is duplication in this result. For example, [1,2,2'] and [1,2',2] should only be counted as the same arrangement, but are Counted as two different permutations. So the key now is, how to design the pruning logic to remove this duplication? The answer is, Ensure that the relative position of the same elements in the arrangement remains unchanged. For example, in nums = [1,2,2'], I keep 2 always in front of 2’ in the arrangement. In this case, you can only pick 3 permutations from the above 6 permutations that meet this condition:
[ [1,2,2'],[2,1,2'],[2,2',1] ]
This is also the correct answer. Furthermore, if nums = [1,2,2',2''], I only need to ensure that the relative position of the repeated element 2 is fixed, for example, 2 -> 2' -> 2' ', you can also get the full arrangement result without duplication
The reason why repetitions occur in the standard total permutation algorithm is because the permutation sequences formed by the same elements are regarded as different sequences, but in fact they should be the same; and if the order of the sequences formed by the same elements is fixed, it will of course be avoided. Repeat
//Newly added pruning logic, fixing the relative position of the same elements in the arrangement
if (i > 0 & amp; & amp; nums[i] == nums[i - 1] & amp; & amp; !used[i - 1]) {<!-- -->
// If the previous adjacent equal elements have not been used, skip
continue;
}
//Select nums[i]
When duplicate elements appear, such as entering nums = [1,2,2',2''], 2′ will only be selected if 2 has already been used. According to the principle, 2” will only be selected if 2′ has already been used, which ensures that the relative position of the same elements in the arrangement is fixed
Code implementation
Give the code to implement the basic file
Basic data structure: Array
Auxiliary data structure: None
Algorithm: Backtracking Algorithm
Tips: None
import java.util.*;
public class Solution {<!-- -->
//Define result set
private ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
//Define path collection and use identification collection
ArrayList<Integer> path = new ArrayList<Integer>();
/**
* The class name, method name, and parameter name in the code have been specified. Please do not modify them. Just return the value specified by the method.
*
*
* @param num int integer one-dimensional array
* @return int integer ArrayList<ArrayList<>>
*/
public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {<!-- -->
// 1 Define the occupancy list
boolean[] used = new boolean[num.length];
// 2 Sort the existing collection to ensure that duplicate elements are adjacent
Arrays.sort(num);
// 3 Perform path search and result set supplementation
backTrack(num, used);
return result;
}
private void backTrack( int[] num, boolean[] used) {<!-- -->
// 1 Termination condition, reaching the leaf node
if (path.size() == num.length) {<!-- -->
result.add(new ArrayList<Integer>(path));
return;
}
// 2 Path tracing and supplementation of this layer
for (int i = 0; i < num.length; i + + ) {<!-- -->
// 1 Prune, used elements maintain relative position
if (i > 0 & amp; & amp; num[i] == num[i - 1] & amp; & amp; !used[i - 1]) {<!-- -->
continue;
}
//Standard pruning logic
if (used[i]) {<!-- -->
continue;
}
// 2 path supplement
path.add(num[i]);
used[i] = true;
// 3 Continue to the next level to search
backTrack(num, used);
// 4 Trace back after return
path.remove(path.size() - 1);
used[i] = false;
}
}
}
Complexity analysis
Permutations II (Permutations II) is a permutation problem. Different from the above-mentioned total permutation problem, the input array num here may contain duplicate elements. The code that solves this problem also uses a backtracking algorithm, but requires special considerations when dealing with duplicate elements. The following is the time complexity and space complexity analysis of the total permutation II problem:
Time complexity:
-
Similar to the total permutation problem, the time complexity of the backtracking algorithm depends on the depth of the recursion and the number of operations at each level of recursion.
-
At each level of recursion, all elements in the
numarray need to be traversed. Since there may be duplicate elements, you need to ensure that the same element is only considered once in the same level of recursion. Therefore, in each level of recursion, some methods can be adopted to skip repeated elements, thereby reducing the number of traversal operations. -
The depth of the recursion still depends on the size of the
numarray, which isn. -
In the worst case, the recursion will go as deep as
nlevels, so the total time complexity is stillO(n * n!), but since duplicate elements are taken into account, The actual number of operations performed may be less than for the total permutation problem.
Space complexity:
-
The space complexity mainly depends on the depth of the recursive call and the data structure used to store the intermediate results.
-
The depth of recursion is
n, so there will be at mostnlevels of recursion frames in the call stack. Each recursive frame includes ausedarray and apatharray, both of which have space complexity ofO(n). -
Since there are
nlevels of recursive frames, the total space complexity isO(n^2).
To sum up, the time complexity of full permutation II is still O(n * n!), where n is the input array num size, the space complexity is O(n^2). Again, due to the nature of the total permutation problem, this time complexity is acceptable in the worst case, although repeated elements are taken into account. However, the actual number of operations may be less than in the full permutation problem because identical elements are skipped.
Expand knowledge: backtracking algorithm problem-solving framework
Abstractly speaking, solving a backtracking problem is actually the process of traversing a decision tree. Each leaf node of the tree stores a legal answer. You can get all legal answers by traversing the entire tree and collecting all the answers at the leaf nodes. Standing at a node in the backtracking tree, you only need to think about 3 questions:
- Path: This is the choice that has been made.
- Choice list: This is the choices you can make at the moment.
- End condition: That is, the condition when the bottom layer of the decision tree is reached and no more choices can be made.
The framework of the backtracking algorithm:
result = []
def backtrack(path, selection list):
if the end condition is met:
result.add(path)
return
for select in selection list:
make decisions
backtrack(path, selectlist)
Unselect
Itscore is the recursion in the for loop, “making a selection” before the recursive call, and “undoing the selection” after the recursive call