// Runtime: 0 ms, faster than 100.00% of Java online submissions for Permutations.
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new LinkedList<>();
        go(0, nums, results);
        return results;
    }

    private void go(int from, int[] nums, List<List<Integer>> results) {
        if (from >= nums.length) {
            List<Integer> r = new ArrayList<Integer>(nums.length);
            for (int num: nums) r.add(num);
            results.add(r);
            return;
        }

        int first = nums[from];
        for (int k = from; k < nums.length; k++) {
            nums[from] = nums[k];
            nums[k] = first;

            go(from + 1, nums, results);

            nums[k] = nums[from];
        }
        nums[from] = first;
    }
}