/*

Author: Timon Cui, [email protected]

Title: Permutations

Description:

Difficulty rating: Easy

Notes:

Solution:

For each permutation of num[1:], insert num[0] to all possible locations.

Solution2:

For each i, num[i] + permute(num[:i] + num[i + 1:]) is a valid permutation.

There are other solutions based on couting i from 0 to N!,

and consider i as a N - 1 digit number denoted as:

i = 0 * v0 + 1 * v_1 + 2 * v_2 + 6 * v_3 + 24 * v4 + ... + (N - 1)! * v_{N - 1}

where v_k = 0, ..., k denotes the index to choose for the (N - k)-th element

in the permutation.

This only works when N is small because the integer would overflow.

The best method is to use the next_permutation method to generate proper indices:

https://github.com/timoncui/LeetCode/blob/master/Next_Permutation.cpp

*/

class Solution {

public:

vector<vector<int> > permute(vector<int> &num) {

if (num.size() == 1) return vector<vector<int> >(1, num);

vector<int> rest(num.begin() + 1, num.end());

vector<vector<int> > part = permute(rest);

vector<vector<int> > result;

for (int i = 0; i < part.size(); ++i) {

for (int j = 0; j <= part[i].size(); ++j) {

vector<int> p = part[i];

p.insert(p.begin() + j, num[0]);

result.push_back(p);

}

}

return result;

}

};

class Solution2 {

public:

vector<vector<int> > permute(vector<int> &num) {

if (num.size() == 1) return vector<vector<int> >(1, num);

vector<vector<int> > result;

for (int i = 0; i < num.size(); ++i) {

vector<int> sub = num;

sub.erase(sub.begin() + i);

vector<vector<int> > p = permute(sub);

for (int j = 0; j < p.size(); ++j) {

p[j].push_back(num[i]);

result.push_back(p[j]);

}

}

return result;

}

};