1.思路：

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

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

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

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

具体做法：

  • step 1：先将数组排序，获取字典序最小的排列情况。
  • step 2：递归的时候根据当前下标，遍历后续的元素，交换二者位置后，进入下一层递归。
  • step 3：处理完一分支的递归后，将交换的情况再换回来进行回溯，进入其他分支。
  • step 4：当前下标到达数组末尾就是一种排列情况。
class Solution {
public:
    void recursion(vector<vector<int> > &res, vector<int> &num, int index){
        //分枝进入结尾，找到一种排列
        if(index == num.size()-1)
        {
            res.push_back(num);
        }
        else {
            //遍历后续的元素
            /*
            刚开始index = 0,这样就相当于把之后的每一个元素（包括自己，因为i也是从index开始，一开始自己与自己交换）都提到第一个位置进行一次全排序，后面的递归中index逐渐增加，也就是用同样的方式实现了每一层的结果，直到只剩2个元素，最后两个元素不交换是一种结果，一交换是第二种结果
            例如 index = num.size()-2,i = index时不交换,进入下一递归，此时进入结尾，存入该结果
            i = index +1 时交换，进入结尾后，存入该结果，这样就是两种结果，最后递归逐渐回调，得到最终结果
            此外，最重要的步骤就是回溯，因为递归回调以后的数组是swap改变过的数组，此时就要重新再次swap这两个数，以使数组变回原样以进行下一次i与index的交换。
            每次递归回调都会将之前改变的数组重新变为原样，这样也就给之后的排序建立方便
            */
            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) {
        vector<vector<int> > res;
        sort(num.begin(),num.end());
        recursion(res, num, 0);
        return res;
    }
};