46. Permutations (Medium)

Given a collection of distinct 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],
  [3,2,1]
]

Solution 1: DFS 13ms

class Solution {
    // permute num[begin..end]
    // invariant: num[0..begin-1] have been fixed/permuted
    void dfs(vector<int>& nums, int begin, vector<vector<int>>& res) {
        if (begin == nums.size()) {
            // one permutation instance
            res.push_back(nums); return;
        }
        for (int i = begin; i < nums.size(); ++i) {
            swap(nums[begin], nums[i]);
            dfs(nums, begin+1, res);
            swap(nums[begin], nums[i]); // reset
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        dfs(nums, 0, res);
        return res;
    }
};

Solution 2: Insertion

最后再来看一种方法，这种方法是CareerCup书上的方法，也挺不错的，这道题是思想是这样的：

当n=1时，数组中只有一个数a1，其全排列只有一种，即为a1

当n=2时，数组中此时有a1a2，其全排列有两种，a1a2和a2a1，那么此时我们考虑和上面那种情况的关系，我们发现，其实就是在a1的前后两个位置分别加入了a2

当n=3时，数组中有a1a2a3，此时全排列有六种，分别为a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, 和 a3a2a1。那么根据上面的结论，实际上是在a1a2和a2a1的基础上在不同的位置上加入a3而得到的。

_ a1 _ a2 _ : a3a1a2, a1a3a2, a1a2a3

_ a2 _ a1 _ : a3a2a1, a2a3a1, a2a1a3

version 1: recursion 13ms

class Solution {
public:
    vector<vector<int>> permute(vector<int>& num) {
        if (nums.empty()) return {{}};

        vector<vector<int>> res;
        int first = nums[0];
        nums.erase(nums.begin());

        vector<vector<int>> words = permute(nums);
        for (auto& a: words) {
            for (int i = 0; i <= a.size();++i) {
                a.insert(a.begin()+i, first);
                res.push_back(a);
                a.erase(a.begin()+i);
            }
        }
        return res;
    }
};

version 2: iterative 22ms

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.empty()) return {{}};

        vector<vector<int>> res = {{nums[0]}};

        for (int i = 1; i < nums.size(); ++i) { // insert nums[i]
            vector<vector<int>> tmp;
            for (int j = 0; j <= i; ++j) { // insert position
                for (auto& a: res) {
                    a.insert(a.begin()+j, nums[i]);
                    tmp.push_back(a);
                    a.erase(a.begin()+j);
                }
            }
            res = tmp;
        }
        return res;
    }
};