Leetcode - Permutations ( Java)
Tags: Algorithm, LeetCode, Permutation, recursionGiven a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
|
1 2 3 4 5 6 7 8 9 |
[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ] |
Analysis
I will use an example to illustrate how to generate all the permutation of an array.
Given a list [1, 2, 3, 4], all the permutations consists of the four sets:
the permutations starts with 1: {1} + {permutations of array [2, 3, 4]}
the permutations starts with 2,
the permutations starts with 3,
the permutations starts with 4,
Suppose we have a function called search to generate permutations for the subarray
nums[start .. end]. We first call
seach([1, 2, 3, 4]), the answer will be the union of the following four sets:|
1 2 3 4 5 6 7 |
[1] + {search([2, 3, 4])}, [2] + {search([1, 3 ,4]}, [3] + {search[2, 1, 4]}, [4] + {search([2, 3, 1]} |
To implement this recursive algorithm, we can use the back tracking idea. The following is the pseudo code:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
search(int[] A, int start, res){ if start == A.length - 1, //this means the subarray is A[A.length-1 .. A.length - 1] //so there is only one element left in the subarray, Now the elements in A is a permutation of the original array. // we just copy the values in A into res. else { for( int i = start; i < A.length; i++) { // let A[i] in the beginning swap(A, start, i) // continue generate the permutation for the subarray A[start + 1, ... end] search(a, start + 1, res) // this is the backtracking step. After this step, the array is restored to the initial state: A[start .. end], // so the value at start index can be swapped with the next value (A[i + 1]) in the next round. // that means, in the next round, A[i + 1] will be put in the beginning of the array. swap(A, start, i) } } } |
Java 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 26 27 28 29 30 31 32 33 34 35 36 |
public class Permutation { public List<List<Integer>> permute(int[] nums) { List<List<Integer>> res = new ArrayList<>(); search(nums, 0, res); return res; } void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } public void search(int[] nums, int start, List<List<Integer>> res) { if(start == nums.length - 1) { List<Integer> list = new ArrayList<>(); for(int num:nums) { list.add(num); } res.add(list); return; } for(int i = start; i < nums.length; i++) { swap(nums, start, i); search(nums, start + 1, res); swap(nums, start, i); } } public static void main(String[] args) { int[] A = {1,2, 3}; System.out.println(new Permutation().permute(A)); } } |
Another algorithm to generate permutation, it is easier to understand, but it is slower as it uses more space.
|
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 26 27 28 29 30 31 32 33 34 35 36 |
class Permutation2 { public List<List<Integer>> permute(int[] nums) { return solve(nums, 0); } List<List<Integer>> solve(int[] nums, int start){ if(start == nums.length -1){ List<Integer> item = new ArrayList<Integer>(); item.add(nums[nums.length-1]); List<List<Integer>> list = new ArrayList<List<Integer>>(); list.add(item); return list; } List<List<Integer>> res = new ArrayList<List<Integer>>(); for(int i = start; i < nums.length ; i++){ swap(nums, start, i); List<List<Integer>> list = solve(nums, start+1); for(List<Integer> item: list){ item.add(nums[start]); res.add(item); } swap(nums, start, i); } return res; } void swap(int[] nums, int i, int j){ int t = nums[i]; nums[i] = nums[j]; nums[j] = t; } } |
