1、思路

• 这道题通常做法是开一个bool类型的状态数组，标记每个元素是否使用过；

• 仔细观察可以发现，求不同全排列的问题其实是可以利用交换数组元素来完成的；

• 若数组长度为n，将第一个元素分别与后面每一个元素进行交换，生成n种不同的全排列；再用第二个元素与后面每一个元素进行交换，生成n - 1种不同的全排列……

2、代码

class Solution {
public:
    void dfs(vector<int>& nums, int i, vector<vector<int>>& res)
    {
        if (i == nums.size())       //已经遍历到最后一个元素，存储该全排列
        {
            res.push_back(nums);
        }
        else
        {
            for (int j = i; j < nums.size(); ++ j)
            {
                swap(nums[i], nums[j]);     //分别与后面的每一个元素交换
                dfs(nums, i + 1, res);
                swap(nums[i], nums[j]);     //还原成没有与当前元素交换的情况
            }
        }
    }

    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;

        dfs(nums, 0, res);

        return res;
    }
};