LeetCode-全排列 II（C++）

47. 全排列 II

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

示例 1：
输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

解题思路：

这道题在全排列的基础上更进一步，多了一步去重，如下图所示。

先给数组排好序，在树的同一层，如果它的前一个元素值与它相同，则当前元素不继续往下遍历，跳过该元素。

我们可以定义一个used数组，标识元素是在同一树枝使用过，还是在同一树层使用过，used[i]=true表示同一树枝使用过，used[i]=false表示同一树层使用过。

这道题同一树枝使用过的元素和一样的元素同一树层使用过的我们都要跳过。

代码：

class Solution {	//47. 全排列 II
public:
	vector<vector<int>> result;
	vector<int> path;
	void backtracking(vector<int> const& nums, vector<bool>& used) {
		if (path.size() == nums.size()) {
			result.push_back(path);
			return;
		}

		for (int i = 0; i < nums.size(); ++i){
			if (used[i] == true) continue;
			if (i > 0 && nums[i] == nums[i - 1] && used[i-1]==false) continue;
			used[i] = true;
			path.push_back(nums[i]);
			backtracking(nums, used);
			path.pop_back();
			used[i] = false;
		}
	}
	vector<vector<int>> permuteUnique(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		vector<bool> used(nums.size(), false);
		backtracking(nums, used);
		return result;
	}
};
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

参考资料：代码随想录