46. Permutations

问题

Given a collection of distinct numbers, return all possible permutations.

例子

[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]
]

分析

1. 使用next permutation不断生成下一个排列；
2. backtracing。假设集合中有n个不同的元素，交换n次集合中的元素可以生成一个排列。下图是一棵典型的backtracing tree：

从左向右不断枚举交换元素的情况

要点

next permutation/backtracing

时间复杂度

1. next permutation: O(n!*n)
2. backtracing: O(n!)

空间复杂度

1. next permutation: O(1)
2. backtracing: O(n!)

代码

1.next permutation

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int fact = 1;
        for (int i = 1; i <= nums.size(); i++)
            fact *= i;
            
        res.push_back(nums);
        for (int i = 0; i < fact - 1; i++) {
            nextPermutation(nums);
            res.push_back(nums);
        }
        
        return res;
    }
    
private:
    void nextPermutation(vector<int>& nums) {
        if (nums.size() < 2) return;
        
        int p, q;
        for (p = nums.size() - 2; p >= 0; p--)
            if (nums[p] < nums[p + 1]) break;
        if (p == -1) { 
            reverse(nums.begin(), nums.end());
            return;
        }
        
        for (q = nums.size() - 1; q > p; q--)
            if (nums[q] > nums[p]) break;
        swap(nums[p], nums[q]);
        reverse(nums.begin() + p + 1, nums.end());
    }
};

2.backtracing

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> permutations;
        permute(nums, 0, permutations);
        return permutations;
    }
    
private:
    void permute(vector<int> &nums, int begin, vector<vector<int>> &permutations) {
        if (begin == nums.size() - 1) {
            permutations.push_back(nums);
            return;
        }
        for (int i = begin; i < nums.size(); i++) {
            swap(nums[i], nums[begin]);
            permute(nums, begin + 1, permutations);
            swap(nums[i], nums[begin]);
        }
    }
};