Permutations@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, 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].

» Solve this problem

刚开始想不用递归做，没想出来。后来参考了“水中的鱼” 的解法，用递归，关键点是要存储每一次的permutation，所以用值传递来传递参数，这样就不用把一堆string合并在一起再返回，也节约了运算时间。这类recursion还得多设计，熟练起来。

	class Solution {
	public:
	void findPermute(vector<int> & num, int step, vector<int>& visited, vector<int>& solution, vector<vector<int> >& coll)
	{
	if(step==num.size())
	{
	coll.push_back(solution);
	return;
	}
	for(int i=0; i<num.size(); i++)
	{
	if(visited[i]==0)
	{
	visited[i]=1;
	solution.push_back(num[i]);
	findPermute(num, step+1, visited, solution, coll);
	solution.pop_back();
	visited[i]=0;
	}
	}
	}
	vector<vector<int> > permute(vector<int> &num) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	vector<int> solution;
	vector<int> visited(num.size(), 0);
	vector<vector<int> > coll;
	if(num.empty()) return coll;
	findPermute(num, 0, visited, solution, coll);
	return coll;
	}
	};

view raw Permutations hosted with ❤ by GitHub