BM55. [没有重复项数字的全排列]

https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295

BM55. 没有重复项数字的全排列

https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1?tpId=295&sfm=discuss&channel=nowcoder

题目主要信息:

• 给定一个数组，求这组数字的全排列
• 数组无重复元素
• 以数字在数组中的位置靠前为优先级，按字典序排列输出

具体思路:

全排列就是对数组元素交换位置，使每一种排列都可能出现。因为题目要求按照字典序排列输出，那毫无疑问第一个排列就是数组的升序排列，它的字典序最小，后续每个元素与它后面的元素交换一次位置就是一种排列情况，但是如果要保持原来的位置不变，那就不应该从它后面的元素开始交换而是从自己开始交换才能保证原来的位置不变，不会漏情况。如下图所示：

如何保证每个元素能和从自己开始后的每个元素都交换位置，这种时候我们可以考虑递归。为什么可以使用递归？我们可以看数组[1,2,3,4],如果遍历经过一个元素2以后，那就相当于我们确定了数组到该元素为止的前半部分，前半部分1和2的位置都不用变了，只需要对3，4进行排列，这对于后半部分而言同样是一个全排列，同样要对从每个元素开始往后交换位置，因此后面部分就是一个子问题。那我们考虑递归的几个条件：

• 终止条件： 要交换位置的下标到了数组末尾，没有可交换的了，那这就构成了一个排列情况，可以加入输出数组。
• 返回值： 每一级的子问题应该把什么东西传递给父问题呢，这个题中我们是交换数组元素位置，前面已经确定好位置的元素就是我们返还给父问题的结果，后续递归下去会逐渐把整个数组位置都确定，形成一种排列情况。
• 本级任务： 每一级需要做的就是遍历从它开始的后续元素，每一级就与它交换一次位置。

但是，很遗憾如果只是使用递归，我们会发现，上例中的1与3交换位置以后，如果2再与4交换位置的时候，我们只能得到3412这种排列，无法得到1432这种情况。这是因为遍历的时候1与3交换位置在2与4交换位置前面，递归过程中就默认将后者看成了前者的子问题，但是其实我们1与3没有交换位置的情况都没有结束，相当于上述图示中只进行了第一个分支。因此我们用到了回溯。处理完1与3交换位置的子问题以后，我们再将其交换回原来的情况，相当于上述图示回到了父节点，那后续完整的情况交换我们也能得到。

代码实现:

class Solution {
public:
    void recursion(vector<vector<int> > &res, vector<int> &num, int index){
        if(index == num.size() - 1) //分枝进入结尾，找到一种排列
            res.push_back(num);
        else{
            for(int i = index; i < num.size(); i++){ //遍历后续的元素
                swap(num[i], num[index]); //交换二者
                recursion(res, num, index + 1); //继续往后找
                swap(num[i], num[index]); //回溯
            }
        }
    }

    vector<vector<int> > permute(vector<int> &num) {
        sort(num.begin(), num.end()); //先按字典序排序
        vector<vector<int> > res;
        recursion(res, num, 0); // 递归获取
        return res;
    }
};

复杂度分析：

• 时间复杂度：，n个元素的数组进行全排列
• 空间复杂度：，递归栈的最大深度为数组长度n，res属于返回必要空间