首页 > 代码库 > 【leetcode】Permutations

【leetcode】Permutations

问题:

Given a collection of numbers, return all possible permutations.

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

分析:

permutations II 里的 一样,这里排个序就很简单,一样的代码提交,同能通过,看来,考察的应该不是如此简单。
这里给个不排序的吧,其实还是用的排序的原理,只是嫁接了一层。

实现:

  vector<vector<int> > permute(vector<int> &num) {
    const int len = num.size();

	vector<vector<int> > re;
	re.push_back(num);
	vector<int> index;
	
	if(len <= 1)
		return re;
		
	int i = len - 1;
	for (int n = 0; n < len; ++n)
	{
		index.push_back(n);
	}
	//reserve num, we don't plan to change it.
	vector<int> cp(num);
	while (1)
	{
		int ii = i;
		--i;
		if(i < 0 )
		{
			return re;
		}
		if(index[ii] > index[i]){
			int j = len - 1;
			while (index[j] < index[i]) --j;
			swap(index[i], index[j]);
			//you can write a reverse function yourself.
			//Reverse(num, ii, len - 1);
			reverse(index.begin() + ii,index.end());
			for (int n = 0; n < len; ++n)
			{
				cp[n] = num[index[n]];
			}
			re.push_back(cp);
			i = len - 1;
		}
	
	}
}