/*
https://leetcode.com/problems/permutations/
Runtime: 37 ms, faster than 5.01% of Java online submissions for Permutations.
Memory Usage: 37.4 MB, less than 95.74% of Java online submissions for Permutations.
*/
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        ArrayList<List<Integer>> output = new ArrayList<>();
        List<Integer> numbers = Arrays.stream(nums).boxed().collect(Collectors.toList());
        for (int step = 0, il = factorial(nums.length); step < il; step++) {
            output.add(new ArrayList<>(numbers));
            int i = nums.length - 2;
            while (i > -1 && numbers.get(i) >= numbers.get(i + 1)) {
                --i;
            }
            if (i > -1) {
                int j = i + 1;
                while (j < nums.length && numbers.get(i) < numbers.get(j)) {
                    ++j;
                }
                Collections.swap(numbers, i, j - 1);
            }
            for (int s = i + 1, e = nums.length - 1; s < e; ++s, --e) {
                Collections.swap(numbers, s, e);
            }
        }
        return output;
    }

    static int factorial(int n) {
        int result = 1;
        for (int i = 1; i <= n; i++) {
            result *= i;
        }
        return result;
    }
}