Leetcode 46 Permutations

In this Leetcode problem, we are given an array of distinct integers, and we should return a list of all the permutations for these integers.

Problem statement

Solution

The concept is to resolve the problem recursively by:

1. Pick one element in the list, and remove it from the list of available integers
2. Generate all the permutations for the remaining list and append them to the first element

To do that we keep track of current which is the currently available integers, and permutation, which is the currently generated permutation.

Of course, the time complexity and space is O(n*(n!)) , that’s assuming we can add and remove elements from the working lists efficiently. If you are not sure, use LinkedList which has a better API for removeLast but time is about the same.

Here is the code:

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> current = new ArrayList<>();
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            current.add(nums[i]);
        }
        permuteRec(res, current, new ArrayList<>());
        return res;
    }
    
    public void permuteRec(
        List<List<Integer>> res,
        List<Integer> current…