题目

• 输入一组数字（可能包含重复数字），输出其所有的排列方式。
• 数据范围

输入数组长度 [0,6]。

示例

• 输入：[1,2,3]
• 输出：

  [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
  ]

代码

• DFS 视频讲解

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {
        path.resize(nums.size());
        sort(nums.begin(), nums.end());
        dfs(nums, 0, 0, 0);
        return ans;
    }
    // start 是枚举起始下标  , state 是访问状态
    void dfs(vector<int> &nums, int u, int start, int state){
        if(u == nums.size()){
            ans.push_back(path);
            return;
        }
        if(!u || nums[u] != nums[u-1])  start = 0;
        for(int i = start; i < nums.size(); i++){
            // 看看这一位有没有被访问
            if(!(state >> i & 1)){
                path[i]  = nums[u];
                dfs(nums, u+1, i+1, state + (1 << i));
            }
        }
    }
};

代码分析：理解的不是很透彻，需要多看看，这里面有一些需要注意的地方

if(!u || nums[u] != nums[u-1])  start = 0;

这一句是说如果当前数和上一个数不重复，那么这个数的位置可以随意枚举。我们的要求是，如果当前数和上一个数重复，那么这个数的位置只能放在上一个数的后面，也就是从当前下标往后枚举。

if(!(state >> i & 1)){
    path[i]  = nums[u];
    dfs(nums, u+1, i+1, state + (1 << i));
}

这里!(state >> i & 1)查看该位是否已存在值。

dfs(nums, u+1, i+1, state + (1 << i));

这里的最后一个参数state + (1 << i)是把该位标志已有值。

题目：数字排列