题目
输入一组数字（可能包含重复数字），输出其所有的排列方式。
样例
输入：[1,2,3]
输出：
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解法：dfs

需要注意重复数字的情况，排列数目会减少
先将所有数字排序，这样可以将相同的数字放在一起
接着，我们约定相同的数字由左向右摆放
为此，我们引入变量start记录当前数字开始搜索的位置
时间复杂度O(nlogn)，空间复杂度O(n2)

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        path.resize(nums.size());
        dfs(nums, 0, 0, 0);
        return ans;
    }
    void dfs(vector<int> &nums, int p, int start, int state) {
        if (p == nums.size()) {
            ans.push_back(path);
            return;
        }
        if (!p || nums[p] != nums[p - 1]) start = 0;
        for (int i = start; i < nums.size(); i++) {
            if (!(state >> i & 1)) {
                path[i] = nums[p];
                dfs(nums, p + 1, i + 1, state | 1 << i);
            }
        }
    }
};