Permutations

Given a collection of numbers, return all possible permutations.

[1,2,3] will have the following permutations:

[1,2,3]
[1,3,2]
[2,1,3] 
[2,3,1] 
[3,1,2] 
[3,2,1]

Method:

In each level, we assume the number before that level is fixed, and then we swap numbers with current level to get all possibilities.

Solution:

Time: O(n!)
Space: O(n!)

public class Solution {
    public ArrayList<ArrayList<Integer>> permute(ArrayList<Integer> A) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        helper(result, A, 0);
        return result;
    }
    
    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> A, int index) {
        if (index == A.size()) {
            result.add(new ArrayList<>(A));
            return;
        }
        for (int i = index; i < A.size(); i ++) {
            Collections.swap(A, index, i);
            helper(result, A, index + 1);
            Collections.swap(A, index, i);
        }
    }
}

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, result, 0);
        return result;
    }
    
    private void backtrack(int[] nums, List<List<Integer>> result, int start) {
        if (start == nums.length) {
            List<Integer> list = new ArrayList<>(nums.length);
            for (int n : nums) list.add(n);
            result.add(list);
            return;
        }
        for (int i = start; i < nums.length; i ++) {
            swap(nums, i, start);
            backtrack(nums, result, start + 1);
            swap(nums, i, start);
        }
    }
    
    private void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}