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++) {
            int add = orig.at(index);
            perm_cp.insert(perm_cp.begin() + i, add);
            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