LeetCode 46 全排列

LeetCode 46 全排列

https://leetcode-cn.com/problems/permutations/

因为题目明确说明没有重复数字并且有了LeetCode 31的铺垫，这道题也就成了easy级别的题目了。同样地，我们可以使用标准库和手写排列生成算法两种方式来解题。当然了，也可以参照力扣题解，使用回溯法来解题，但这里就不写回溯法的代码了。

使用标准库

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;

        sort(nums.begin(), nums.end());
        do { ans.push_back(nums); } 
        while (next_permutation(nums.begin(), nums.end()));

        return ans;
    }
};

手写排列生成算法

注意到，n个不同数的全排的个数共有n!个，所以我们需要调用n!次生成下一个排列的方法才能将所有的排列生成完全。

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int sz = nums.size();

        // n个不同的数的排列个数有n!个
        unsigned long long total = 1;
        for (int i = 1; i <= sz; ++i) {
            total *= i;
        }

        vector<vector<int>> ans;
        sort(nums.begin(), nums.end());
        while (total--) {
            ans.push_back(nums);
            nextPermutation(nums);
        }
        return ans;
    }

    void nextPermutation(vector<int>& nums) {
        int sz = nums.size();

        int i, j;
        for (i = sz - 2; i >= 0; --i) {
            if (nums[i] < nums[i + 1]) {
                break;
            }
        }
        if (i >= 0) {
            for (j = sz - 1; j > i; --j) {
                if (nums[j] > nums[i]) {
                    break;
                }
            }
            swap(nums[i], nums[j]);
        }

        reverse(nums.begin() + i + 1, nums.end());
    }
};