47. 全排列 II#

1
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
2

3
示例 1：
4

5
输入：nums = [1,1,2]
6
输出：
7
[[1,1,2],
8
 [1,2,1],
9
 [2,1,1]]
10

11
示例 2：
12

13
输入：nums = [1,2,3]
14
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
15

16

17
提示：
18

19
1 <= nums.length <= 8
20
-10 <= nums[i] <= 10

1
class Solution {
2
public:
3
    vector<int> vis;
4

5
    void backtrack(
6
        vector<int>& nums, vector<vector<int>>& ans, int i, vector<int>& res
7
    ) {
8
        int n = nums.size();
9
        if (i == n) {
10
            ans.emplace_back(res);
11
            return;
12
        }
13
        for (int j = 0; j < n; j++) {
14
            if (vis[j] || (j > 0 && nums[j] == nums[j - 1] && !vis[j - 1])) continue;
15
            res.emplace_back(nums[j]);
16
            vis[j] = 1;
17
            backtrack(nums, ans, i + 1, res);
18
            vis[j] = 0;
19
            res.pop_back();
20
        }
21
    }
22

23
    vector<vector<int>> permuteUnique(vector<int>& nums) {
24
        vector<vector<int>> ans;
25
        vector<int> res;
26
        vis.resize(nums.size());
27
        sort(nums.begin(), nums.end());
28
        backtrack(nums, ans, 0, res);
29
        return ans;
30
    }
31
};