46. 全排列

题目

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

解答

方法一：回溯

思路

从高中的数学知识我们可以知道

从[1,2,3]中选出3个数进行排列（排序有顺序之分、组合没有顺序之分）

结果有n！=3！=3*2*1种

怎么计算的呢？

假设现在我们有三个数：1、2、3

需要依次填入下面三个蓝色方块

那么第一个方块有三种选择：1或2或3

第二个有两种选择：2或者3（假设第一次选择了1）

那么第三个方块就只有一种选择：3（假设第一次选择1，第二次选择2）

综上：n个数（不重复），填入n个方块，一共有n！种不同排列方式。

那么为什么第一次有三种而第二次只有两种了呢？

这是因为第一次选择时，没有一个数被选，那么一个三个数，就有三种选择方法

到第二次选择时，因为第一次必定选择了一个数，这时剩下的可供选择的数就只有2个，选择就只有两种了

到第三次选择时，因为前面两次已经选择了两个数，可供选择的数就只有一个，选择就只有一种了

从上面提取核心思想：

每次进行选择时，我们都是从一些尚未选择的数中选择出一个数字填充方块，然后将该数标记为已选择，再进行下一轮新的选择。

根据上述思想，画出下面思路图：

上图若没有理解 没有关系 先看下面

这里我们可以利用一个全局变量temp数组，初始化为空，作为一个临时容器

开始时，1、2、3都是尚未选择的

此时我们可以选择 1 或 2 或 3，有三种选择方法

假设我们选择了1后

那么将1添加至temp中【temp：1】

此时1已经被选择

之后可供我们选择的就是 2、3

再选择2【temp：1-2】

最后再选择3【temp：1-2-3】

此时temp与我们预期的答案吻合【其实就是temp数组的长度与预期结果数组长度一样】

将其添加至res结果数组中即可

在我们的思想中

可以很简单的知道 1被选择 2、3未被选择

但是在程序中，我们如何实现这个呢？

这里我们利用一个数组isused来判定元素是否被选择

假如情况是：1被选择 2、3未被选择

那么原数组与isused数组关系如下：

所以在每次进行选择前，我们利用isused数组，判定某个元素是否被选择

只有未被选择 我们才可以对这个元素进行操作

所以在每次选择前，我们都会扫描isused数组，当为true时，才对该元素进行操作。【具体是true还是false进行操作依据个人习惯而定，这里海轰是true代表未被选择】

根据上面的思路，写出下面的代码：

vector<int> temp;
void backtracking(vector<vector<int>> &res,vector<bool> &isused,vector<int> &nums){
        // 当temp数组的长度等于期望数组的长度时 return
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return ;
        }
        // 遍历所有选择
        for(int i=0;i<nums.size();++i){
            // 对没有选择过的元素再进行抉择：选择它｜不选择它
            if(isused[i]){
            		// 选择该元素 选择后标记该元素为已选择 同时进行下一元素的抉择
                temp.push_back(nums[i]);
                isused[i]=false;
                backtracking(res,isused,nums);
                // 回复原来状态：未选择 同时从temp中pop出 
                isused[i]=true;
                temp.pop_back();
          }
   }
}
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<bool> isused(nums.size(),true);
        backtracking(res,isused,nums);
        return res;
}

运行结果

疑问

疑问1:程序具体是怎么执行的呢？

这里只给出程序的运行简图，

对详细步骤感兴趣对小伙伴可以自己动手画画步骤图

疑问2:为什么当 temp.size()==nums.size()或所有的元素都被选择后 函数backtracking返回呢？

首先

当temp.size()==nums.size()时

代表此时的temp已经满足答案需要

可以将其添加至res中

如果temp.size()<nums.size()

那么意思就是还temp中还需要一些元素

比如要求数组长度是4

此时temp长度只有2

那么就还需要再选择两个数进入temp

其次

当所有的元素都被选择后

说明已经没有元素可以供加入temp中

则必须return

疑问3:为什么 backtracking函数的开头就需要判定temp.size()==nums.size()？而不是在函数中部或者尾部？

首先可以看出

在这里我们用了递归

那么必须要一个递归终止条件

不然递归怎么结束呢？

backtracking作为一个递归函数

我们可以想到

每次进入backtracking函数时

第一要务就是需要判定此时temp的size

如果满足答案要求的长度

将temp压入res数组

再return

后面步骤也就不需要再运行

疑问4:为什么backtracking函数中每次要进行for(int i=0;i<nums.size();++i){}循环？

这里是因为每次进行抉择前

我们需要找出所有未被选择的元素

在这里我们使用的判定数组isused标志选择与否

所以每次都需要循环扫描isused数组【代码中：因为isused数组长度与nums数组一样，这里size写谁都可以】

疑问5:为什么会进行temp.pop_back()？

从代码中

我们可以发现

temp.pop_back()前面有句 backtracking(res,isused,nums,temp);

也就是说

只有backtracking(res,isused,nums,temp) 运行完后

才会进行temp.pop_back()

那么啥时候backtracking(res,isused,nums,temp)会结束呢？

参考疑问2

可以知道

backtracking(res,isused,nums,temp)结束时

代表某个元素已经被选择了，且引进被压入了temp中使用了

额外意思就是该元素已经被使用了

因为每次抉择都有两种：选择与不选择

那么选择结束了

之后肯定就是不选择了

但是此时元素已经被压入了temp中

那么需要怎么办呢？

简单，pop出即可，同时标记isuserd数组为true即可。

改进

改进方案：temp可以不定义为全局变量

代码如下：

void backtracking(vector<vector<int>> &res,vector<bool> &isused,vector<int> &nums,vector<int> &temp){
        // 选择完毕
        if(temp.size()==nums.size()){
            res.push_back(temp);
            return ;
        }
        for(int i=0;i<nums.size();++i){
            if(isused[i]){
                temp.push_back(nums[i]);
                isused[i]=false;
                backtracking(res,isused,nums,temp);
                isused[i]=true;
                temp.pop_back();
            }
    }
}
vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<bool> isused(nums.size(),true);
        vector<int> temp;
        backtracking(res,isused,nums,temp);
        return res;
}

运行结果

改进方案：bool<->int push_back<->emplace_back

isused数组海轰使用的bool变量

在评论区有小伙伴说

当数据量大的时候使用int类型会好一点

同时

在将temp压入res时

使用emplace_back()会好一点

因为不会产生临时变量

代码如下：

vector<int> temp;
    void backtracking(vector<vector<int>> &res,vector<int> &isused,vector<int> &nums){
        // 当temp数组的长度等于期望数组的长度时 return
        if(temp.size()==nums.size()){
            res.emplace_back(temp);
            return ;
        }
        // 遍历所有选择
        for(int i=0;i<nums.size();++i){
            // 对没有选择过的元素再进行抉择：选择它｜不选择它
            if(!isused[i]){
            		// 选择该元素 选择后标记该元素为已选择 同时进行下一元素的抉择
                temp.push_back(nums[i]);
                isused[i]=1;
                backtracking(res,isused,nums);
                // 回复原来状态：未选择 同时从temp中pop出 
                isused[i]=0;
                temp.pop_back();
          }
   }
}
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<int> isused(nums.size());
        backtracking(res,isused,nums);
        return res;
}

运行结果

方式二：回溯（官方题解，动态交换原数组中的元素）

官方题解代码如下：

void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        if (first == len) {
            res.emplace_back(output);
            for(int i=0;i<output.size();++i){
                cout<<output[i]<<" ";
            }
            cout<<endl;
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            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;
    }

运行结果

思路

在官方题解中

并没有向我们使用的依次将元素添加至一个临时数组temp中

而是直接在原数组上进行变换

将变换结果依次加入结果数组res中。

程序具体执行过程如下：

观察每个节点生成的下一个节点，元素是如何交换的？

对for循环进行思考：

当first=0时，此时for循环会进行:swap(nums[0],nums[0])/swap(nums[1],nums[0])/swap(nums[2],nums[0])

当first=1时，此时for循环会进行:swap(nums[1],nums[1])/swap(nums[2],nums[1])

当first=2时，此时for循环会进行:swap(nums[2],nums[2])

        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);// 注意：这里是first+1
            // 撤销操作
            swap(output[i], output[first]);
        }

这里可能会有点难度

不好想象程序时如何进行的？

建议首先自己对照程序跑一次

明白每一次运行的结果

然后再对照上面几张图寻找规律

之后对官方题解就会有所理解了

变式

代码（修改backtracking函数中的返回条件即可）

vector<int> temp;
    void backtracking(vector<vector<int>> &res,vector<bool> &isused,vector<int> &nums){
        // 选择完毕 
        if(temp.size()==3){
            res.push_back(temp);
            return ;
        }
        for(int i=0;i<nums.size();++i){
            if(isused[i]){
                temp.push_back(nums[i]);
                isused[i]=false;
                backtracking(res,isused,nums);
                isused[i]=true;
                temp.pop_back();
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > res;
        vector<bool> isused(nums.size(),true);
        backtracking(res,isused,nums);
        return res;
    }

运行结果

代码2（对官方题解进行修改）：

void backtrack(vector<vector<int>>& res, vector<int>& output, int first, int len){
        // 所有数都填完了
        // 修改结束条件
        if (first == 3) {
            vector<int> temp(output.begin(),output.begin()+3);//利用临时数组存储
            res.emplace_back(temp);
            return;
        }
        for (int i = first; i < len; ++i) {
            // 动态维护数组
            swap(output[i], output[first]);
            // 继续递归填下一个数
            backtrack(res, output, first + 1, len);
            // 撤销操作
            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;
    }

运行结果