算法1

DFS

有2种实现的思路
1. 将nums的数一个一个放到位置上
2. 枚举每个位置放什么数

对于有重复的情况下，使用第一种思路方便些
先将nums 进行排序，然后如果是重复的数字，那么只能往后放。

找组合也可以用这种思想。

C++ 代码

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<int> data;
    vector<bool> mask;
    vector<vector<int>> permutation(vector<int> nums) {
        data = nums;
        mask = vector<bool> (nums.size() , false);
        path = vector<int> (nums.size());
        sort(nums.begin(), nums.end());
        dfs(0,  -1, nums.size());
        return ans;
    }
    void dfs(int pos, int pre, int n) {
        if (pos >= n) {
            ans.push_back(path);
            return;
        }

        int start = 0;
        if (pos - 1 >= 0 && data[pos] == data[pos - 1]) {
            start = pre + 1;
        }

        for (int i = start; i < n; ++i) {
            if (!mask[i]) {
                path[i] = data[pos];
                mask[i] = true;
                dfs(pos + 1, i, n);
                mask[i] = false;
//                path.pop_back();
            }
        }

    }
};