数字的排列问题

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

样例

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

输入：[1,2,3]

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

去重思路

集合 {$1,1,2$}, 得到结果 {$1,1,2$},{ $1,2,1$ }, {$2,1,1$}

1 和 1 只要保持相对位置不变，就不会产生重复的序列

也就是说，第一次 选了 第1个1， 第2个1就不能排到 第1 个1 的前面，只能排到 前面那个1 的后面

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    #define ll long long
    // vector<int> vis;
    int n;
    vector<vector<int>>res;
    vector<int> path;
    vector<vector<int>> permutation(vector<int>& nums) {
       
        sort(nums.begin() ,nums.end()) ;
        n = nums.size();
        path.resize(n);
        dfs(0,0, nums,0);
        return res;
    }
    
    void dfs(int pathLen ,int start,vector<int>& nums,int vis) {
        if(pathLen >= n) {
            res.push_back(path);
            return;
        }
        
        if(pathLen == 0 || nums[pathLen] != nums[pathLen - 1]) start = 0;
        //从头开始选择
        for(int i=start;i<n;++i) {
            if( ! (vis>>i &  1) ) {
                path[i] = nums[pathLen];
                dfs(pathLen + 1, i+1,nums, vis+ (1<<i));
                
            }
        }
        
    }
     
};