[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
Post a Comment