Permutations.cpp

/*
 Author:     Weixian Zhou, ideazwx@gmail.com
 Date:       Jul 10, 2012
 Problem:    Permutations
 Difficulty: easy
 Source:     http://www.leetcode.com/onlinejudge
 Notes:
 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:
 There is a same time complexity but with more simple code solution provided by
 https://github.com/anson627/leetcode/blob/master/Permutations/src/Permutations.cpp
 All permutations can be generated by swapping.
 */
#include <vector>
#include <set>
#include <climits>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstring>
#include <list>
using namespace std;

class Solution {
public:
	bool *available;
	vector<vector<int> > result;
	vector<int> permutation;
	int n;
	void recursion(int dep, vector<int> &num) {
		if (dep == n) {
			result.push_back(permutation);
			return;
		}
		int i = 0;
		while (i < n) {
			if (available[i]) {
				available[i] = false;
				permutation.push_back(num[i]);
				recursion(dep + 1, num);
				available[i] = true;
				permutation.pop_back();
			}
			i++;
		}
	}
	vector<vector<int> > permute(vector<int> &num) {
		vector<int> permutation;
		n = num.size();
		available = new bool[n];
		for (int i = 0; i < n; i++) {
			available[i] = true;
		}
		result.clear();
		recursion(0, num);

		return result;
	}
};