# LeetCode - 0046. Permutations
### 題目網址：https://leetcode.com/problems/permutations/
###### tags: `LeetCode` `Medium` `數學` `排列組合`

/*
    -LeetCode format-
    Problem: 46. Permutations
    Difficulty: Medium
    
    by Inversionpeter
*/



void nextPermutation(vector<int> &numbers) {
    static int firstMinimum, minimumAt;
    for (int i = numbers.size() - 2; i >= 0; --i)
        if (numbers[i] < numbers[i + 1]) {
            firstMinimum = 2147483647;
            for (int j = i + 1; j != numbers.size(); ++j)
                if (numbers[i] < numbers[j] && firstMinimum > numbers[j]) {
                    firstMinimum = numbers[j];
                    minimumAt = j;
                }
            swap(numbers[i], numbers[minimumAt]);
            sort(numbers.begin() + i + 1, numbers.end());
            return;
        }
    sort(numbers.begin(), numbers.end());
}

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        int amount = 1;
        for (int i = 1; i <= nums.size(); ++i)
            amount *= i;
        vector <vector <int>> answer(amount);
        for (int i = 0; i < amount; ++i) {
            answer[i] = nums;
            nextPermutation(nums);
        }
        return answer;
    }
};