LeetCode Q46 Permutations

Given a collection of distinct 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].

Easy question, but should be careful when it comes to a solution using recursion. 

Two solutions.

• Using recursion

Using recursion, every time just insert the current element to the head of the results returned from subproblems. Otherwise there are redundancies. 

	vector<vector<int> > permute(vector<int>& nums){
	vector<vector<int> > results;
	if(nums.size()==1){
	vector<int> r;
	r.push_back(nums[0]);
	results.push_back(r);
	return results;
	}
	for(int i=0; i<nums.size(); ++i){
	vector<int> newnums=nums;
	newnums.erase(newnums.begin()+i);
	vector<vector<int> >tmpresults=permute(newnums);
	for(int j=0; j<tmpresults.size(); ++j){
	vector<int> tmptmpr=tmpresults[j];
	tmptmpr.insert(tmptmpr.begin(), nums[i]);
	results.push_back(tmptmpr);
	}
	}
	return results;
	}

view raw Q46Permutation1.cpp hosted with ❤ by GitHub

• Not using recursion

Building up the results by insert element one by one.

	class Solution {
	public:
	vector<vector<int> > permute(vector<int>& nums){
	vector<vector<int> > results(1, vector<int>(1, nums[0]));
	for(int i=1; i<nums.size(); ++i){
	int v=nums[i];
	vector<vector<int> > tmpresults;
	for(int j=0; j<results.size(); ++j){
	for(int k=0; k<=results[j].size(); ++k){
	vector<int> r=results[j];
	r.insert(r.begin()+k, v);
	tmpresults.push_back(r);
	}
	}
	results=tmpresults;
	}
	return results;
	}
	};

view raw Q462.cpp hosted with ❤ by GitHub