leetcode47.全排列 II

Posted on | In |
Words count in article: 282 | Reading time ≈ 1

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

示例：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

分析：

1
2
3
4
5
DFS：
搜索顺序：按位置从0开始搜索
剪枝：
	- st[i]表示字符是否被使用过
	- 先排序使相同字符相邻，i && nums[i] == nums[i - 1] && !st[i - 1]表示如果该字符和前一个相同，同时上一个没有用过则跳过，即把两个字符看成一个整体

代码

  • C++

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
class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    vector<bool> st;
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        st.resize(nums.size());
        sort(nums.begin(), nums.end());
        dfs(0, nums.size(), nums);

        return res;
    }

    void dfs(int u, int n, vector<int>& nums) {
        if (u == n) {
            res.push_back(path);
            path.empty();
            return;
        }

        for (int i = 0;i < n;i ++) {
            if (st[i]) continue;
            if (i && nums[i] == nums[i - 1] && !st[i - 1]) continue;
            st[i] = true;
            path.push_back(nums[i]);
            dfs(u + 1, n, nums);
            st[i] = false;
            path.pop_back();
        }

    }
};

[原题链接](47. 全排列 II - 力扣（Leetcode）)

0%