46. 全排列

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

示例:
输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

枚举每一个数字放在哪一位

这个例子比较特殊，代码和下面的一样，只有一行不同：

// 数组第 u 个元素放在第 i 个位置
path[i] = nums[u];

枚举每一位放哪个数字

class Solution {
public:
    vector<bool> st;
    vector<vector<int>> ans;
    vector<int> path;
    int n;
    vector<vector<int>> permute(vector<int>& nums) 
    {
        n = nums.size();
        st.resize(n, false), path.resize(n);

        dfs(nums, 0);

        return ans; 
    }

    void dfs(vector<int>& nums, int u)
    {
        if(u == n)
        {
            ans.push_back(path);
            return;
        }
        // st 数组记录的是数组下标是否被用过
        for(int i = 0; i < n; ++i)
            if(!st[i])
            {
                st[i] = true;
                // 数组第 i 个元素放在第 u 个位置
                path[u] = nums[i];
                dfs(nums, u + 1); 
                st[i] = false;
            }
    }
};