Leetcode – Permutations ( Java)

Tags: , , ,

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

 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:
 

To implement this recursive algorithm, we can use the back tracking idea. The following is the pseudo code:

 

Java solution:

Another algorithm to  generate permutation,  it is easier to understand, but it is slower as it uses more space.