# 46 Permutations

Given a collection ofdistinctnumbers, 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],
[3,2,1]
]
The Idea: Recursively append the `i+1th` element to every position for every permutation in the previous set of permutations until the end is reached.
Complexity: O(n! * n)
vector<vector<int>> _permute(vector<vector<int>> &prev, const vector<int> &orig, int index) {
if (index >= orig.size()) return prev;
vector<vector<int>> next;
next.reserve((prev[0].size() + 1) * prev.size());
for (auto perm : prev) {
vector<int> perm_cp = perm;
for (int i = 0; i <= perm.size(); i++) {
next.push_back(perm_cp);
perm_cp = perm;
}
}
return _permute(next, orig, index + 1);
}
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> permutations;
if (nums.empty()) return permutations;
permutations.push_back(vector<int>(1,nums[0]));
return _permute(permutations, nums, 1);
}
Python
class Solution:
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
sol = [[]]
for n in nums:
next_sol = []
for prev in sol:
# ab, ba
for i in range(0, len(prev) + 1):
# cab, acb, abc
next_sol.append(prev[:i] + [n] + prev[i:])
sol = next_sol
return sol