Permutations II@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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].

» Solve this problem

关键就是去掉重复的。 我的方法是用hashtable， unordered_map<vector<int>, bool> hm;

遇到一个在hashmap里没有的，我就insert一个，每次遇到一个permutation我都检查一下hashmap里面有了木有。可惜俺不会specialize hash，搞了半天，网上找了几个都不work out，我对这个不熟，因为vector<int> 不是hashmap已有的参数。于是还是参照了 别人的code。求大神告诉我肿么 specialize....

	class Solution {
	public:
	void uniquePermutation(vector<int> &num, int step, vector<int> &visited, vector<int> &solution, vector<vector<int> > &res)
	{
	if(step==num.size())
	{
	res.push_back(solution);
	//hm[solution]=true;
	return;
	}
	for(int i=0; i<num.size(); i++)
	{
	if(visited[i]==0)
	{
	if(i>0 && num[i]==num[i-1] && visited[i-1]==0)
	continue;
	visited[i]=1;
	solution.push_back(num[i]);
	uniquePermutation(num, step+1, visited, solution, res);
	solution.pop_back();
	visited[i]=0;
	}
	}
	}
	vector<vector<int> > permuteUnique(vector<int> &num) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> visited(num.size(), 0), solution;
	vector<vector<int> > res;
	//unordered_map<vector<int>, bool> hm;
	if(num.empty()) return res;
	sort(num.begin(), num.end());
	uniquePermutation(num, 0, visited, solution, res);
	return res;
	}
	};

view raw permutations II hosted with ❤ by GitHub