LeetCode Q47: Permutation II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

The idea to distinguish this question with Q46 is that we never insert a duplicate element before previous appeared duplicated element. Say nums[i], nums[i+1] are equal, we first insert nums[i], when inserting nums[i+1], we only insert it to places that are after nums[i]. To do so, we have to keep tracking the position of each insertion. The trick I use here is to save this information to the last element of each vector.

	class Solution {
	public:
	void helper(vector<int>& nums, int c, vector<vector<int> >& res){
	if(c==nums.size()){
	for(int i=0; i<res.size(); ++i)
	res[i].erase(res[i].begin()+res[i].size()-1);
	return;
	}
	vector<vector<int> >newres;
	for(int i=0; i<res.size(); ++i){
	int pos=res[i][res[i].size()-1];//get pos
	res[i].erase(res[i].begin()+res[i].size()-1);//remove from vector
	pos=(nums[c]==nums[c-1])?pos+1:0;
	for(int j=pos; j<=res[i].size(); ++j){
	vector<int> r=res[i];
	r.insert(r.begin()+j, nums[c]);
	r.push_back(j);
	newres.push_back(r);
	}
	}
	res=newres;
	if(c!=nums.size())
	helper(nums, ++c, res);
	}
	vector<vector<int> > permuteUnique(vector<int>& nums){
	sort(nums.begin(), nums.end());
	vector<vector<int> > res;
	if(nums.empty())
	return res;
	vector<int> r;
	r.push_back(nums[0]);
	r.push_back(0); // use last digit to store pos.
	res.push_back(r);
	helper(nums, 1, res);
	return res;
	}
	};

view raw Q47PuermuationII.cpp hosted with ❤ by GitHub

Solution 3: Recursion. Each iteration, remove one element from given nums, and add the number to current result.

	class Solution {
	public:
	void helper(vector<vector<int> >& res, vector<int>& tmpRes, vector<int>& nums){
	if(nums.size()==0){
	res.push_back(tmpRes);
	return;
	}
	for(int i=0; i<nums.size(); i++){
	tmpRes.push_back(nums[i]);
	int tmp = nums[i];
	swap(nums[i], nums[nums.size()-1]);
	nums.pop_back();
	helper(res, tmpRes, nums);
	nums.push_back(tmp);
	swap(nums[i], nums[nums.size()-1]);
	tmpRes.pop_back();
	}
	}
	vector<vector<int>> permute(vector<int>& nums) {
	vector<vector<int> > res;
	if(nums.empty())
	return res;
	vector<int> tmpRes;
	helper(res, tmpRes, nums);
	return res;
	}
	};

view raw Q46-3.cpp hosted with ❤ by GitHub

Round 2 Solution:
In round 2, I have been forming my own code pattern when solving such kind of problems. To solve skip duplicate elements, I will first finish recursion part followed by a loop which will check duplicate elements and move index to skip duplicate elements.

	class Solution {
	public:
	void helper(vector<vector<int> >& res, vector<int>& tmpRes, vector<int>& nums, vector<int>& label){
	if(tmpRes.size()==nums.size()){
	res.push_back(tmpRes);
	return;
	}
	for(int i=0; i<nums.size(); i++){
	if(label[i]==1)
	continue;
	label[i]=1;
	tmpRes.push_back(nums[i]);
	helper(res, tmpRes, nums, label);
	tmpRes.pop_back();
	label[i]=0;
	while(i<=nums.size()-2&&nums[i]==nums[i+1]) i++;
	}
	}
	vector<vector<int>> permuteUnique(vector<int>& nums) {
	sort(nums.begin(), nums.end());
	vector<int> label(nums.size(), 0);
	vector<vector<int> > res;
	if(nums.empty())
	return res;
	vector<int> tmpRes;
	helper(res, tmpRes, nums, label);
	return res;
	}
	};

view raw Q47-3.cpp hosted with ❤ by GitHub