Recursion / backtracking (Part 1)

One 、 A full arrangement of numbers without duplicates

Solution 1 : recursive + to flash back ( recommend )

• for example [1,2,3,4], If you traverse through elements 2 after , First half part 1 and 2 Your position will remain the same , Yes 3,4 Sort , The second half is equivalent to a full arrangement , That is, the sub problem
• When it reaches the end of the array
• Use recursion and backtracking at the same time , Return to start making different branch selections

public:
    void fun(vector<vector<int>>&tmp,vector<int>&num,int index)
    {
    
        int n=num.size();
        if(index==n-1)// Branch into the end to find an arrangement 
            tmp.push_back(num);
        else
        {
    
            for(int i=index;i<n;i++)
            {
    
                swap(num[i],num[index]);// In exchange for 
                fun(tmp,num,index+1);// Keep looking back 
                swap(num[i],num[index]);// to flash back 
            }
        }
    }
    vector<vector<int> > permute(vector<int> &num) {
    
        sort(num.begin(),num.end());// Ascending row 
        vector<vector<int>>tmp;
        fun(tmp,num,0);// Ground cabinet acquisition 
        return tmp;
    }
};

Time complexity ：O(n∗n!), The approximate O(n^2),n The array of elements is recursively arranged in full , Every recursion must traverse the array
Spatial complexity ：O(n), The maximum depth of recursive stack is array length n,tmp It belongs to returning the necessary space

Solution 2 : Library function

Use next_permutation Make a full arrangement

class Solution {
    
public:
    vector<vector<int> > permute(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<vector<int>>v;
        do{
    
            v.push_back(num);
        }while(next_permutation(num.begin(), num.end()));// Library function 
        return v;
    }
};

Time complexity ：O(n!),n An array of elements is arranged in full
Spatial complexity ：O(1), Return matrix v It belongs to the necessary space , It doesn't belong to extra space

Two 、 A full arrangement of numbers with duplicates

Solution 1 : recursive + to flash back ( recommend )

• First, sort the array in dictionary order
• Prepare an array to temporarily store the arrangement assembled during recursion . Use extra back An array is used to record where numbers are added .
• Each recursion traverses the array from the beginning , Get digital join ： First of all, according to the back Array , Elements that have been added cannot be added again ; meanwhile , If the current element num[i] The previous element on the same layer num[i-1] Same and num[i-1] Has been used , Nor does it need to be included in .
• Before going to the next level of recursion back The current position of the array is marked as used .
• It needs to be modified during backtracking back Array current position marker , At the same time, remove the elements just added to the array ,
• When the length of the temporary array reaches the length of the original array, it is an arrangement .

class Solution {
    
public:
    void fun(vector<vector<int>>&res,vector<int>&num,vector<int>&tmp,vector<int>back)
    {
    
        if(tmp.size()==num.size())// When the temporary array is full, add the output 
        {
    
            res.push_back(tmp);
            return;
        }
        for(int i=0;i<num.size();i++)
        {
    
            if(back[i])// If the element has been added , No re-entry required 
                continue;
            if(i>0&&num[i-1]==num[i]&&!back[i-1])//num[i] and num[i-1] It has been used 
                continue;
            back[i]=1;// Mark as used 
            tmp.push_back(num[i]);
            fun(res,num,tmp,back);
            back[i]=0;// to flash back 
            tmp.pop_back();
        }
    }
    vector<vector<int> > permuteUnique(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<int>back(num.size(),0),// Initialization is not used 
        tmp;
        vector<vector<int>>res;
        fun(res,num,tmp,back);
        return res;
    }
};

Time complexity ：O(n∗n!), All cases of full arrangement are n!, Each recursive process is to traverse the array to find elements , Here is O(n)
Spatial complexity ：O(n), The maximum depth of recursive stack is array length n, Temporary array temp The space is also O(n),res It belongs to returning the necessary space

Solution 2 : Library function

class Solution {
    
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<vector<int>>res;
        do{
    
            res.push_back(num);
        }while(next_permutation(num.begin(), num.end()));
        return res;
    }
};

Use the same as the first question
Time complexity ：O(n!),n An array of elements is arranged in full
Spatial complexity ：O(1), Return matrix res It belongs to the necessary space , It doesn't belong to extra space

3、 ... and 、 Realize it by yourself next_permutation

class Solution {
    
public:
    bool mynext_Permutation(vector<int> &num) {
    
    int i = num.size() - 2;
    while (i >= 0 && num[i] >= num[i + 1]) {
    
        i--;
    }
    if (i < 0) {
    
        return false;
    }
    int j = num.size() - 1;
    while (j >= 0 && num[i] >= num[j]) {
    
        j--;
    }
    swap(num[i], num[j]);
    reverse(num.begin() + i + 1, num.end());
    return true;
    }

    vector<vector<int> > permuteUnique(vector<int> &num) {
    
        sort(num.begin(),num.end());
        vector<vector<int>>res;
        do{
    
            res.push_back(num);
        }while(mynext_Permutation(num));
        return res;
    }
};

Time complexity ：O(n!),n An array of elements is arranged in full
Spatial complexity ：O(1), Return matrix res It belongs to the necessary space , It doesn't belong to extra space