## 编程知识 cdmana.com

### Backtracking algorithm clique out subset, permutation and combination problem

78. A subset of

46. Full Permutation

77. Combine

-----------

Today, I'll talk about three high frequency investigations , And the confusing algorithm problem , They are subsets （subset）, Please arrange （permutation）, Find combination （combination）.

These problems can be solved by backtracking algorithm template , At the same time, the subset problem can also be solved by mathematical induction . Readers can remember the backtracking routine of these questions , I'm not afraid we can't make it clear .

### One 、 A subset of

The problem is simple , Enter a Does not contain repeating numbers Array of , The algorithm is required to output all subsets of these numbers .

``````vector<vector<int>> subsets(vector<int>& nums);
``````

Such as input `nums = [1,2,3]`, Your algorithm should output 8 A subset of , Contains empty sets and itself , The order can be different ：

[ [],,,,[1,3],[2,3],[1,2],[1,2,3] ]

The first solution is to use the idea of mathematical induction ： Suppose I now know the result of a smaller subproblem , How to deduce the result of the current problem ？

To be specific , Now let's ask for `[1,2,3]` Subset , If you know `[1,2]` Subset , Can we deduce `[1,2,3]` A subset of ？ The first `[1,2]` Let's see a subset of ：

[ [],,,[1,2] ]

You will find such a law ：

subset(`[1,2,3]`) - subset(`[1,2]`)

= ,[1,3],[2,3],[1,2,3]

And the result , Is to put sebset(`[1,2]`) Each set in the result is added with 3.

let me put it another way , If `A = subset([1,2])` , that ：

subset(`[1,2,3]`)

= A + [A[i].add(3) for i = 1..len(A)]

This is a typical recursive structure ,`[1,2,3]` A subset of can be made up of `[1,2]` Add to get ,`[1,2]` A subset of can be made up of `` Add to get ,base case Obviously, when the input set is empty , The output subset is also an empty set .

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

It's easy to understand when translated into code ：

``````vector<vector<int>> subsets(vector<int>& nums) {
if (nums.empty()) return {{}};
//  Take the last element out
int n = nums.back();
nums.pop_back();
//  Let's recursively work out all the subsets of the previous elements
vector<vector<int>> res = subsets(nums);

int size = res.size();
for (int i = 0; i < size; i++) {
//  Then add... To the previous results
res.push_back(res[i]);
res.back().push_back(n);
}
return res;
}
``````

The time complexity of this problem is easy to be calculated . What we said before is how to calculate the time complexity of recursive algorithm , Is to find the depth of recursion , Then multiply by the number of iterations in each recursion . For this question , The depth of recursion is obviously N, But every time we find recursion for The number of iterations of the loop depends on `res` The length of , It's not fixed .

According to the thinking just now ,`res` Should be twice as long as every recursion , So the total number of iterations should be 2^N. Or not so much trouble , Think of a size of N There are several subsets of the set of ？2^N Right , So at least right `res` add to 2^N Sub elements .

So the time complexity of the algorithm is O(2^N) Do you ？ It's still not right ,2^N The subset is `push_back` Added to the `res` Of , So consider `push_back` The efficiency of this operation ：

``````for (int i = 0; i < size; i++) {
res.push_back(res[i]); // O(N)
res.back().push_back(n); // O(1)
}
``````

because `res[i]` It's also an array ,`push_back` It's a `res[i]` copy A copy is then added to the end of the array , So the time of an operation is O(N).

Sum up , The total time complexity is O(N*2^N), It's still time consuming .

In terms of space complexity , If the space used to store the returned results is not calculated , It only needs O(N) The recursive stack space of . If calculation `res` The space needed , Should be O(N*2^N).

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

The second general method is backtracking algorithm . Old language 「 Detailed explanation of backtracking algorithm 」 Write the template of backtracking algorithm ：

``````result = []
def backtrack( route ,  Selection list ):
if  Meet the end condition :
return
for  choice  in  Selection list :
To make a choice
backtrack( route ,  Selection list )
Unselect
``````

Just change the template of backtracking algorithm ：

``````vector<vector<int>> res;

vector<vector<int>> subsets(vector<int>& nums) {
//  Record the path
vector<int> track;
backtrack(nums, 0, track);
return res;
}

void backtrack(vector<int>& nums, int start, vector<int>& track) {
res.push_back(track);
for (int i = start; i < nums.size(); i++) {
//  To make a choice
track.push_back(nums[i]);
//  to flash back
backtrack(nums, i + 1, track);
//  Unselect
track.pop_back();
}
}
``````

Can see , Yes `res` The update position is in the preorder traversal , in other words ,`res` It's all the nodes on the tree ### Two 、 Combine

Enter two numbers `n, k`, Algorithm output `[1..n]` in k All combinations of numbers .

``````vector<vector<int>> combine(int n, int k);
``````

Such as input `n = 4, k = 2`, The output is as follows , Order doesn't matter , But it can't contain repetition （ According to the definition of combination ,`[1,2]` and `[2,1]` It's a repetition ）：

[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]

This is also a typical backtracking algorithm ,`k` Limits the height of the tree ,`n` It limits the width of the tree , Continue to use the template framework of backtracking algorithm that we talked about before ： ``````vector<vector<int>>res;

vector<vector<int>> combine(int n, int k) {
if (k <= 0 || n <= 0) return res;
vector<int> track;
backtrack(n, k, 1, track);
return res;
}

void backtrack(int n, int k, int start, vector<int>& track) {
//  Get to the bottom of the tree
if (k == track.size()) {
res.push_back(track);
return;
}
//  Be careful  i  from  start  Began to increase
for (int i = start; i <= n; i++) {
//  To make a choice
track.push_back(i);
backtrack(n, k, i + 1, track);
//  Unselect
track.pop_back();
}
}
``````

`backtrack` Functions are similar to subsets of computation , The difference lies in , to update `res` When the tree reaches the bottom .

### 3、 ... and 、 array

Enter a Does not contain repeating numbers Array of `nums`, Return all the permutations of these numbers .

``````vector<vector<int>> permute(vector<int>& nums);
``````

For example, input array `[1,2,3]`, The output should be as follows , Order doesn't matter , There can be no repetition ：

[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

「 Detailed explanation of backtracking algorithm 」 This question is used to explain the backtracking template . Here's a list of the questions , Yes, it will 「 array 」 and 「 Combine 」 Compare the codes of these two backtracking algorithms .

First draw a backtree to see ： We used Java The solution of code writing ：

``````List<List<Integer>> res = new LinkedList<>();

/*  The main function , Enter a set of non repeating numbers , Return to their full array  */
List<List<Integer>> permute(int[] nums) {
//  Record 「 route 」
backtrack(nums, track);
return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
//  Trigger end condition
if (track.size() == nums.length) {
return;
}

for (int i = 0; i < nums.length; i++) {
//  Rule out illegal choices
if (track.contains(nums[i]))
continue;
//  To make a choice
//  Go to the next decision tree
backtrack(nums, track);
//  deselect
track.removeLast();
}
}
``````

The backtracking template still hasn't changed , But according to the tree drawn by permutation problem and combination problem , The tree of permutation problem is more symmetrical , And the tree of combinatorial problem is closer to the right, the fewer nodes .

This is reflected in the code , Arrange questions every time they pass `contains` Method to exclude in `track` Number already selected in ; And the combinatorial question passes in a `start` Parameters , To exclude `start` Number before index .

PS： I've seriously written about 100 Multiple original articles , Hand brush 200 Daoli is the subject , All published in labuladong A copy of the algorithm , Continuous updating . Recommended collection , Write the title in the order of my article , Master all kinds of algorithm set, then put into the sea of questions, like fish .

above , It's the solution to the three problems of permutation, combination and subset , To sum up

Subset problems can be solved by mathematical induction , Suppose we know the result of a smaller problem , Think about how to deduce the result of the original problem . You can also use backtracking algorithm , Use `start` Parameter to exclude the selected number .

Combinatorial problems use the idea of backtracking , The result can be expressed as a tree structure , We just need to apply the backtracking algorithm template , The key point is to use a `start` Exclude numbers that have been selected .

The problem of alignment is to think back , It can also be expressed as tree structure applying algorithm template , The key point is to use `contains` Method to exclude the selected number , There is a detailed analysis of , This is mainly compared with the combination problem .

Remember the shapes of these trees , It's enough to deal with most backtracking algorithms , does `start` perhaps `contains` prune , There's no other technique .

＿＿＿＿＿＿＿＿＿＿＿＿＿

my Online e-books Yes 100 Original articles , Hands with brushes 200 Daoli is the subject , Recommended collection ！ Corresponding GitHub Algorithm Repository We've got it 70k star, Welcome to mark star ！

Scroll to Top