算法

(DFS)

对于全排列，比如[1,2,3]的全排列，我们按顺序穷举，步骤如下：
1. 首先会固定第一位为 $1$，然后第二位如果取$2$，最后一位只能是$3$；再可以把第二位变成$3$，第三位就只能是$2$
2. 接下来把第一位变成 $2$，然后再像上述的过程穷举后两位分别是$1,3$
3. 最后第一位是$3$，再穷举后两位分别是$1,2$，整个过程就完成了

C++ 代码

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int> > results;

        // 如果数组为空直接返回空
        if (nums.size() == 0) {
            results.push_back(vector<int>());
            return results;
        }

        // dfs
        vector<bool> used(nums.size(), 0);
        vector<int> current;
        dfs(nums, used, current, results);

        return results;
    }

    void dfs(vector<int> nums, vector<bool> &used, vector<int> &current, vector<vector<int> > &results) {
        //找到一组排列，已到达边界条件
        if (current.size() == nums.size()) {
            results.push_back(current);
            return;
        }

        for (int i = 0; i < nums.size(); i++) {
            // i位置这个元素已经被用过
            if (used[i]) {
                continue;
            }

            //继续递归
            current.push_back(nums[i]);
            used[i] = true;
            dfs(nums, used, current, results);
            used[i] = false;
            current.pop_back();
        }
    }
};

// Ver2: 调用STL
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>>ans;
        sort(nums.begin(),nums.end());
        ans.push_back(nums);
        while(next_permutation(nums.begin(),nums.end())){
            ans.push_back(nums);
        }
        return ans;
    }
};