31_Next_permutation

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        for (int i = nums.size() - 1; i >= 1; --i){
            if (nums[i] > nums[i - 1]){
                // need to increase nums[i - 1] by one step (from i - 1 to end)
                int smallest = i;
                for (int j = i + 1; j < nums.size(); ++j){
                    if (nums[j] < nums[smallest] && nums[j] > nums[i - 1]){
                        smallest = j;
                    }
                }
                swap(nums[i - 1], nums[smallest]);
                sort(nums.begin() + i, nums.end());
                return;
            }
        }
        for (int i = 0; i < nums.size(); ++i){
            if (i < nums.size() - i - 1){
                swap(nums[i], nums[nums.size() - i - 1]);
            }
            else{
                return;
            }
        }
    }
};

class Solution {

public:
    void nextPermutation(vector<int>& nums) {
        if (nums.empty()) return;
        for (int i = nums.size() - 1; i >= 0; --i){
            if (nums[nums.size() - 1] <= nums[i]){
                nums.push_back(nums[i]);
                nums.erase(nums.begin() + i);
            }else if (nums[nums.size() - 1] > nums[i]){
                for (int j = i + 1; j < nums.size(); ++j){
                    if (nums[j] > nums[i]){
                        swap(nums[i], nums[j]);
                        return;
                    }
                }
            }
        }
    }
};