[LeetCode] 46. Permutations

Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Thought process:
Recursively add numbers to a list. If the list's size reaches the size of the collection, add the list to the result list. Remove the last number in the list and continue with the recursion.

Solution:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> permutations = new ArrayList<>();
        List<Integer> permutation = new ArrayList<>();
        permute(nums, permutation, permutations);
        
        return permutations;
    }
    
    private void permute(int[] nums, List<Integer> permutation, List<List<Integer>> permutations) {
        if (permutation.size() == nums.length) {
            permutations.add(new ArrayList<>(permutation));
        }
        
        for (int num : nums) {
            if (permutation.contains(num)) {
                continue;
            }
            
            permutation.add(num);
            permute(nums, permutation, permutations);
            permutation.remove(permutation.size() - 1);
        }
    }
}

Time complexity: O(n! * n).

Comments

Popular posts from this blog

[LeetCode] 631. Design Excel Sum Formula

[LeetCode] 269. Alien Dictionary

[LeetCode] 714. Best Time to Buy and Sell Stock with Transaction Fee