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


Solution :
This is done recursively by making permutations resulting from swapping of two elements. The below diagram can make it clear.

We start with k=0 and swap the element at ith index with element at kth index.

At the first level for k = 0, we swap num[k] with num[i] where i varies from k to number of elements in the array. We do this at all levels where value of k increases till it is equal to the number of elements in the array.

Here is the program for it :

	class Solution {
	public:
	vector<vector<int> > permute(vector<int> &num) {
	vector<vector<int>> result;
	perm(num, 0, num.size()-1, result);
	return result;
	}
	void perm( vector<int> &num, int k, int n, vector<vector<int>> &result)
	{
	int i,t;
	if (k==n) result.push_back(num);
	else{
	for(i=k; i<=n;i++)
	{
	t=num[k]; num[k]=num[i]; num[i]=t;
	perm (num, k+1, n, result);
	t=num[k]; num[k]=num[i]; num[i]=t;
	}
	}
	}
	};

view raw permutaions.cpp hosted with ❤ by GitHub

Please comment to add something.