Leetcode: Permutations

 

One of the Leetcode questions that I have done was the following: 

Given an array nums of distinct integers, return all the possible permutations.

 You can return the answer in any order. 

Example 1: Input: nums = [1,2,3] 

Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] 

Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] 

Example 3: Input: nums = [1] Output: [[1]] Constraints: 1 <= nums.length <= 6 -10 <= nums[i] <= 10 

All the integers of nums are unique.

this calls for a recursive solution, where everything is permuted until one solution is finished. When this happens, return the function and move on to all the elements until we're  done.  It is as follows: 

public class Solution {

   public List<List<Integer>> permute(int[] nums) {

List<List<Integer>> permutations = new ArrayList<>();

       

       //if there are no permutations, then return the list.

if (nums.length == 0) {

return permutations;

}

       //invoke the permutation method

collectPermutations(nums, 0, new ArrayList<>(), permutations);

       

       //return the modified arrayList.

return permutations;

    }

private void collectPermutations(int[] nums, int start, List<Integer> permutation,

  List<List<Integer>>  permutations) {

        //if permutation is filled add this to the list.

if (permutation.size() == nums.length) {

permutations.add(permutation);

return;

}

    

        //otherwise, add the start element of the index to the list and recursively call the function.

for (int i = 0; i <= permutation.size(); i++) {

List<Integer> newPermutation = new ArrayList<>(permutation);

newPermutation.add(i, nums[start]);

collectPermutations(nums, start + 1, newPermutation, permutations);

}

}

}