描述

给出一组数字，返回该组数字的所有排列
例如：
[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 0 < n \le 60<n≤6
要求：空间复杂度 O(n!)O(n!) ，时间复杂度 O(n!）O(n!）

示例1

输入： 
[1,2,3]
复制
返回值： 
[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
复制

示例2

输入： 
[1]
复制
返回值： 
[[1]]
解题思路：
1、全排列的套路要记熟！！！
2、因为要按字典序排列，所以每次都应该从0开始查询，只要不是重复元素，就插入到临时数组中
当临时数组满时，就入栈结果数组。
DFS算法需要考虑的三个问题：
1、路径：也就是已经做出的选择。（对应代码的tmp数组，以及每个元素入栈前检查是否重复）
2、选择列表：也就是你当前可以做的选择。（每个非重复数都在选择列表中）
3、结束条件：也就是到达决策树底层，无法再做选择的条件。（当tmp中长度与原数组长度相等时，说明本次选择完成，可以结束）

class Solution {
public:
    vector<vector<int> > res;
    
    void dfs(vector<int> &num, vector<int> &tmp) {
        if (tmp.size() == num.size()) {
            res.push_back(tmp);
            return;
        }
       for (int i = 0; i < num.size(); i++) {
           if (find(tmp.begin(), tmp.end(), num[i]) != tmp.end()) {
               continue;
           }
           tmp.push_back(num[i]);
           dfs(num, tmp);
           tmp.pop_back();  
       }
    }

    vector<vector<int> > permute(vector<int> &num) {
        vector<int> tmp;
        dfs(num,  tmp);
        return res;
    }
};