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.
Subset【MID】
Elements are not duplicated and cannot be selected. First, let’s look at a combinatorial subset tree
Question stem
Basic, cannot contain duplicate, non-checkable subsets
Problem-solving ideas
The combination problem and the subset problem are actually equivalent. Original problem-solving idea. We will not consider how to implement it in code for the time being. First, recall our high school knowledge. How to push all subsets by hand? First, generate a subset with 0 elements, that is, the empty set [], which I call S_0 for convenience of expression. Then, based on S_0, generate all subsets with an element number of 1, which I call S_1
Next, we can derive S_2 based on S_1, that is, all subsets with 2 elements
Why does the set [2] only need to add 3, but not the previous 1? Because the order of the elements in the set does not matter, there is only 3 after 2 in [1,2,3]. If you add the previous 1, then [2,1] will be combined with the previously generated child. The set [1,2] is repeated, In other words, we prevent repeated subsets by ensuring that the relative order between elements remains unchanged, Then, we can deduce S_3 through S_2. In fact, there is only one set [1,2,3] in S_3, which is derived through [1,2]. The entire derivation process is such a tree 
Pay attention to the characteristics of this tree:If the root node is regarded as the 0th level, and the elements on the branches between each node and the root node are used as the value of the node, then the nth level All nodes of are all subsets of size n. For example, your subset of size 2 is the value of the node in this layer.
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 {<!-- -->
// final result set
private List<List<Integer>> result = new LinkedList<>();
//Define path storage set
List<Integer> path = new LinkedList<>();
/**
* 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 n int integer type the n
* @return int integer type
*/
public List<List<Integer>> subsets(int[] nums) {<!-- -->
backtrack(nums, 0);
return result;
}
private void backtrack(int[] nums, int start) {<!-- -->
// 1 result is added to the result set
result.add(new LinkedList<>(path));
// 2 Traverse to find the result set
for (int i = start; i < nums.length; i + + ) {<!-- -->
// 2-1 Execute selection
path.add(nums[i]);
// 2-2 Continue to explore downwards. The start here is i + 1, which indicates that the lower path is selected from the next element.
backtrack(nums, i + 1);
// 2-3 Unselect
path.remove(path.size() - 1);
}
}
}
We use the start parameter to control the growth of branches to avoid duplicate subsets, use track to record the value of the path from the root node to each node, and at the same time collect the path value of each node at the preorder position to complete the traversal of the backtracking tree. All subsets collected
Complexity analysis
This code is a backtracking algorithm for generating all subsets of an array of integers. The algorithm generates subsets recursively, and each time there are two choices in the recursion: include the current element or not include the current element. The following is an analysis of the code:
-
The
subsetsmethod is the public entry point and accepts an integer arraynumsas input and returns a list containing all subsets. -
In the
subsetsmethod, an emptypathlist is created to store the current subset, and then thebacktrackmethod is called to start the backtracking process. -
The
backtrackmethod is a recursive function used to generate subsets. It takes the following steps:-
Add the current
pathto the final result setresult, and add the elements in the currentpathto the result set to represent a subset. -
Iterate over the
numsarray, starting atstart, and for each element, do the following:-
Add the current element to
pathto select the current element. -
The
backtrackmethod is called recursively, but this timestartstarts ati + 1, which ensures that elements are not reused in the same subset. -
Deselect, remove the element you just added from
path, and continue traversing the next element.
-
-
-
The backtracking algorithm recursively generates all possible subsets until all elements in the
numsarray are traversed. -
Ultimately, the
subsetsmethod returns aresultlist containing all subsets.
Time complexity:
- The time complexity mainly depends on the number of recursive calls. For each element, there are two choices, including or not, and each state requires O (n) construction time, so the time complexity is
O(2^n), wherenis the size of the input arraynums.
Space complexity:
-
The space complexity mainly depends on the depth of the recursive call and the data structure used to store intermediate results. The depth of the recursion is at most
n, so the space complexity isO(n). -
Additionally, the space complexity of the
pathlist also needs to be considered. In the worst case, the length of thepathlist may be equal ton, since each element may be included in a subset. Therefore, the total space complexity isO(n).
Summary: This code uses the backtracking algorithm to generate all subsets of the input array nums, with a time complexity of O(2^n) and a space complexity of O(n).
Combination【MID】
Elements are not duplicated and cannot be selected. You are given an input array nums = [1,2…,n] and a positive integer k. Please generate all subsets of size k.
Question stem
Problem-solving ideas
Still taking nums = [1,2,3] as an example, I just asked you to find all subsets, which means collecting the values of all nodes;Now you only need to consider the 2nd layer (the root node as the 0th Collecting the nodes of layer) are all combinations of size 2:
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 {<!-- -->
// final result set
private List<List<Integer>> result = new LinkedList<>();
//Define path storage set
List<Integer> path = new LinkedList<>();
/**
* 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 n int integer type the n
* @return int integer type
*/
public List<List<Integer>> combine(int n, int k) {<!-- -->
// 2 initial value for backtracking
backtrack(n, 1, k);
return result;
}
private void backtrack( int n, int start, int k) {<!-- -->
// 1 result is added to the result set
if (path.size() == k) {<!-- -->
result.add(new LinkedList<>(path));
return;
}
// 2 Traverse to find the result set
for (int i = start; i <= n; i + + ) {<!-- -->
// 2-1 Execute selection
path.add(i);
// 2-2 Continue to explore downward. The start here is i + 1, which indicates that the lower path is selected from the next element.
backtrack(n, i + 1, k);
// 2-3 Unselect
path.remove(path.size() - 1);
}
}
}
Complexity analysis
Time complexity and space complexity are the same as above
Subset II
Elements are repeated and cannot be selected. Let’s briefly add the situation of repeated elements
Problem-solving ideas
Take nums = [1,2,2] as an example. In order to distinguish the two 2 as different elements, we will write nums = [1,2,2’] later. Draw the tree structure of the subset according to the previous idea. Obviously, two adjacent branches with the same value will cause duplication.
The result is:
[
[],
[1],[2],[2'],
[1,2],[1,2'],[2,2'],
[1,2,2']
]
You can see that the two results [2] and [1,2] are repeated, so we need to prune. If a node has multiple adjacent branches with the same value, only the first one will be traversed, and the remaining branches will be traversed. Cut off everything below, don’t go over it
Reflected in the code, needs to be sorted first so that the same elements are close together. If nums[i] == nums[i-1] is found, skip , consistent with the idea of total permutation II
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 {<!-- -->
// final result set
private List<List<Integer>> result = new LinkedList<>();
//Define path storage set
List<Integer> path = new LinkedList<>();
/**
* 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 n int integer type the n
* @return int integer type
*/
public List<List<Integer>> subsetsWithDup(int[] nums) {<!-- -->
// 1 Array sorting, elements with the same value are adjacent
Arrays.sort(nums);
//2 Initial value for backtracking
backtrack(nums, 0);
return result;
}
private void backtrack( int[] nums, int start) {<!-- -->
// 1 result is added to the result set
result.add(new LinkedList<>(path));
// 2 Traverse to find the result set
for (int i = start; i < nums.length; i + + ) {<!-- -->
// 2-1 Pruning, elements that have appeared before will no longer be traversed
if (i > start & amp; & amp; nums[i] == nums[i - 1]) {<!-- -->
continue;
}
// 2-2 Execute selection
path.add(nums[i]);
// 2-3 Continue to explore downward. The start here is i + 1, which indicates that the lower path is selected from the next element.
backtrack(nums, i + 1);
// 2-4 Unselect
path.remove(path.size() - 1);
}
}
}
Complexity analysis
Time and space complexity are the same as above
Combined sum
The element has no duplicates and can be selected. This question is also relatively high-frequency
Question stem
Problem-solving ideas
This question is said to be a combination problem, but in fact it is also a subset problem:Which subset of candidates sums to target? If we want to solve this type of problem, we have to go back to the backtracking tree. We might as well Think about it first, How does the standard subset/combination problem ensure that elements are not reused? The answer lies in the start parameter entered during backtrack recursion.
//Backtracking algorithm framework without recombination
void backtrack(int[] nums, int start) {<!-- -->
for (int i = start; i < nums.length; i + + ) {<!-- -->
// ...
// Recursively traverse the next level of backtracking tree, pay attention to the parameters
backtrack(nums, i + 1);
// ...
}
}
This i starts from start, then the next level of backtracking tree starts from start + 1, thus ensuring that the element nums[start] will not be reused:
Then conversely, if I want each element to be reused, I just change i + 1 to i
// Recombinable backtracking algorithm framework
void backtrack(int[] nums, int start) {<!-- -->
for (int i = start; i < nums.length; i + + ) {<!-- -->
// ...
// Recursively traverse the next level of backtracking tree, pay attention to the parameters
backtrack(nums, i);
// ...
}
}
This is equivalent to adding a branch to the previous backtracking tree. During the process of traversing this tree, an element can be used unlimited times.
Of course, this backtracking tree will grow forever, so our recursive function needs to set a suitable base case to end the algorithm, that is, when the sum of the paths is greater than the target, there is no need to traverse it again
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 {<!-- -->
// final result set
private List<List<Integer>> result = new LinkedList<>();
//Define path storage set
List<Integer> path = new LinkedList<>();
// Define the sum that changes with path storage
int pathSum = 0;
/**
* 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 n int integer type the n
* @return int integer type
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {<!-- -->
if (candidates.length == 0) {<!-- -->
return new LinkedList<>();
}
backtrack(candidates, 0, target);
return result;
}
private void backtrack( int[] nums, int start, int target) {<!-- -->
// 1 equals the target and the result is added to the result set
if (pathSum == target) {<!-- -->
result.add(new LinkedList<>(path));
return;
}
// 2 exceed target and return
if (pathSum > target) {<!-- -->
return;
}
// 3 Traverse to find the result set
for (int i = start; i < nums.length; i + + ) {<!-- -->
// 3-1 Execute selection
path.add(nums[i]);
pathSum + = nums[i];
// 3-2 Continue to explore downwards. The start here is i, which means that the element can be reused.
backtrack(nums, i, target);
// 3-3 Unselect
path.remove(path.size() - 1);
pathSum -= nums[i];
}
}
}
Complexity analysis
Time and space complexity are the same as above
Expand knowledge: Combining subset problems
Whether it is a permutation, combination or subset problem, simply put it is nothing more than asking you to take a number of elements from the sequence nums according to given rules. There are mainly the following variations:
- Form 1. Elements have no duplicates and cannot be re-selected, that is, the elements in nums are all unique, and each element can only be used once at most. This is also the most basic form. Taking combinations as an example, if you enter nums = [2,3,6,7], the only combinations that sum to 7 should be [7]. Full arrangement, subset, combination
- Form 2: Elements can be repeated but not selectable, that is, elements in nums can be repeated, and each element can only be used once at most. Taking combinations as an example, if you enter nums = [2,5,2,1,2], there should be two combinations with a sum of 7 [2,2,2,1] and [5,2]. Full arrangement II, subset II
- Form 3. There are no duplicate elements that can be selected, that is, the elements in nums are unique and each element can be used several times. Taking combinations as an example, if you enter nums = [2,3,6,7], there should be two combinations with a sum of 7 [2,2,3] and [7]. Combined sum
Of course, it can also be said that there is a fourth form, that is, elements can be repeated and selected. But since elements can be selected, why are there repeated elements? After the elements are deduplicated, they are equivalent to Form 3, so this situation does not need to be considered. The example above uses combination problems, but permutation, combination, and subset problems can all have these three basic forms, so there are 9 variations in total.