Leetcode（46）—— Full Permutation

subject

Give an array without duplicate numbers nums , Back to its All possible permutations . You can In any order Return to the answer .

Example 1：

Input ：nums = [1,2,3]
Output ：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2：

Input ：nums = [0,1]
Output ：[[0,1],[1,0]]

Example 3：

Input ：nums = [1]
Output ：[[1]]

Tips ：

• $1$ <= nums.length <= $6$
• $-10$ <= nums[i] <= $10$
• $nums$ All integers in Different from each other

Answer key

Method 1 ： backtracking

Ideas

​​   How to output all the permutations ？ For each current location i, We can swap them anywhere after , Then continue processing the location i+1, Until the last one . In order to prevent every traversal Create a new sub array Storage location i Numbers that have been exchanged before —— We can Using backtracking , Only modify the original array , After the recursion is completed, modify it back .

​​   say concretely , Let's say we've filled in page $\text{first}$ A place , that $\text{nums}$ Array $[0,\text{first}-1]$ Is a collection of filled numbers ,$[\text{first},n-1]$ Is the set of numbers to be filled . We must be trying to use $[\text{first},n-1]$ Fill in the number in $\text{first}$ Number , Suppose the subscript of the number to be filled is $i$, Then when we're done, we'll go to the $i$ Number and number $\text{first}$ Number exchange , That is, it can make it possible to $\text{first}+1$ When we count $\text{nums}$ Array of $[0,\text{first}]$ Part is the number filled in ,$[\text{first}+1,n-1]$ Is the number to be filled in , When you backtrack, you can complete the undo operation by switching back .
​​   A simple example , Suppose we have $[2,5,8,9,10]$ this $5$ The number should be filled in , It has been filled in to $3$ A place , It has been filled in $[8,9]$ Two Numbers , So this array is now $[8,9|2,5,10]$ Such a state , The separator separates the left and right parts . Suppose we fill in this position $10$ The number of , To maintain the array , We will $2$ and $10$ In exchange for , That is, the array can continue to keep the number to the left of the separator has been filled , The one on the right is to be filled in $[8,9,10|2,5]$.

​​   Of course, we will find that the resulting full permutation is not stored in the answer array in dictionary order , If the title requires output in dictionary order , Then please use tag array or other methods .

The following figure shows the whole process of backtracking ：

Code implementation

Leetcode Official explanation ：

class Solution {
    
public:
    void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
    
        //  All the numbers have been filled in 
        if (first == len) {
    
            res.emplace_back(output);
            return;
        }
        for (int i = first; i < len; ++i) {
    
            //  Dynamically maintain arrays 
            swap(output[i], output[first]);
            //  Continue to recursively fill in the next number 
            backtrack(res, output, first + 1, len);
            //  Cancel the operation 
            swap(output[i], output[first]);
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
    
        vector<vector<int> > res;
        backtrack(res, nums, 0, (int)nums.size());
        return res;
    }
};

My own ：

class Solution {
    
    void DFS(vector<vector<int>>& ans, vector<int>& s, vector<int>& nums, int p){
    
        if(s.size() == nums.size()) ans.push_back(s);
        else{
    
            for(int n = p; n < nums.size(); n++){
    
                swap(nums[p], nums[n]);
                s.push_back(nums[p]);
                DFS(ans, s, nums, p+1); //  From the subscript 1 Start 
                s.pop_back();           //  to flash back 
                swap(nums[p], nums[n]);
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
    
        vector<int> s;
        vector<vector<int>> ans;
        DFS(ans, s, nums, 0);
        return ans;
    }
};

After improvement ：

class Solution {
    
    void DFS(vector<vector<int>>& ans, vector<int>& nums, int p){
    
        if(p+1 == nums.size()) 
            ans.push_back(nums);
        else{
    
            for(int n = p; n < nums.size(); n++){
    
                swap(nums[p], nums[n]);
                DFS(ans, nums, p+1);    //  From the subscript  p+1  Start 
                swap(nums[p], nums[n]); //  to flash back 
            }
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
    
        vector<vector<int>> ans;
        DFS(ans, nums, 0);
        return ans;
    }
};

Complexity analysis

• Time complexity ：$O(n\times n!)$, among $n$ Is the length of the sequence .
  The complexity of the algorithm is first affected by $\text{backtrack}$ The number of calls is limited ,$\text{backtrack}$ The number of calls to is ${\sum }_{k=1}^{n}P(n,k)$ Time , among $P(n,k)=\frac{n!}{(n-k)!}=n(n-1)\dots (n-k+1)$, This formula is called n Of k - array , Or partially arranged .
  and ${\sum }_{k=1}^{n}P(n,k)=n!+\frac{n!}{1!}+\frac{n!}{2!}+\frac{n!}{3!}+\dots +\frac{n!}{(n-1)!}<2n!+\frac{n!}{2}+\frac{n!}{2^2}+\frac{n!}{2^{n-2}}<3n!$
  This explanation $\text{backtrack}$ The number of calls is $O(n!)$ Of .
  And for $\text{backtrack}$ Each leaf node called （ common $n!$ individual ）, We need to use the current answer $O(n)$ Copy the time to the answer array , The time complexity of multiplication is $O(n\times n!)$.
  So the time complexity is zero $O(n\times n!)$.
• Spatial complexity ：$O(n)$, among $n$ Is the length of the sequence . Except for the answer array , Recursive functions in the recursive process need to allocate stack space for each layer of recursive functions , So extra space is needed here, and that space depends on the depth of the recursion , Here we can see that the recursive call depth is $O(n)$.