编程知识 cdmana.com

Backtracking algorithm clique out subset, permutation and combination problem

After reading this article , You can go and get the following questions :

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],[2],[3],[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],[1,2] ]

You will find such a law :

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

= [3],[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 [1] 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) {
    // base case, Return to an empty set 
    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 :
        result.add( route )
        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 」
    LinkedList<Integer> track = new LinkedList<>();
    backtrack(nums, track);
    return res;
}

void backtrack(int[] nums, LinkedList<Integer> track) {
    //  Trigger end condition 
    if (track.size() == nums.length) {
        res.add(new LinkedList(track));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        //  Rule out illegal choices 
        if (track.contains(nums[i]))
            continue;
        //  To make a choice 
        track.add(nums[i]);
        //  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 !

版权声明
本文为[labuladong]所创,转载请带上原文链接,感谢

Scroll to Top