[LeetCode] Permutations II

只需要在Permutaitons增加去重的步骤就可以了。那么重复的排列来自哪里呢，比如说我们在选第i位的数的时候，我们选了k，那么当dfs之后我们回来，剩下的数还有k的时候我们有可能又选到k，这样就产生了重复，所以我们要保证排每一位的时候，不要排之前排过的重复的数，那么一个hashset就可以帮我们做到这一点，时间复杂度O(n!)，空间复杂度O(n)（递归深度）代码如下：

解法一：

	class Solution {
	public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
	vector<vector<int>> res;
	permute(nums, 0, res);
	return res;
	}
	private:
	void permute(vector<int>& nums, int i, vector<vector<int>>& res)
	{
	if(i == nums.size())
	{
	res.emplace_back(nums);
	return;
	}
	//unreached part is not definitly to be sorted
	unordered_set<int> marked;
	for(int j = i; j < nums.size(); ++j)
	{
	if(marked.find(nums[j]) != marked.end())
	continue;
	marked.insert(nums[j]);
	swap(nums[i], nums[j]);
	permute(nums, i + 1, res);
	swap(nums[i], nums[j]);
	}
	}
	};

view raw Permutations II_1.cpp hosted with ❤ by GitHub

解法二：

	class Solution {
	public:
	vector<vector<int>> permuteUnique(vector<int>& nums) {
	vector<vector<int>> res;
	vector<int> curr;
	vector<bool> marked(nums.size(), false);
	permute(nums, curr, marked, res);
	return res;
	}
	private:
	void permute(vector<int>& nums, vector<int>& curr, vector<bool>& marked, vector<vector<int>>& res)
	{
	if(curr.size() == nums.size())
	{
	res.emplace_back(curr);
	return;
	}
	unordered_set<int> used;
	for(int i = 0; i < nums.size(); ++i)
	{
	if(!marked[i] && used.find(nums[i]) == used.end())
	{
	used.insert(nums[i]);
	marked[i] = true;
	curr.push_back(nums[i]);
	permute(nums, curr, marked, res);
	curr.pop_back();
	marked[i] = false;
	}
	}
	}
	};

view raw Permutations II_2.cpp hosted with ❤ by GitHub