Permutations
1 min readApr 30, 2019
Question: Given a collection of distinct integers, return all possible permutations.
Example:
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
You may view the full question here.
Approach: Thanks to this brilliant article and the amazing graphic illustration of the operation, here is a simple implementation using recursion—
//Approach
//Runtime: 1ms
//Memory usage: 38.5MBclass Solution {
private List<List<Integer>> result = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
recursive(nums, 0);
return result;
}
private void recursive(int[] n, int start){
if(start==n.length-1){
List<Integer> res = new ArrayList<>();
for(int curr : n){
res.add(curr);
}
result.add(res);
}
for(int i = start;i<n.length; i++){
int[] newN = new int[n.length];
for(int j=0; j<n.length; j++){
newN[j] = n[j];
}
//Swap
int temp = newN[start];
newN[start] = newN[i];
newN[i] = temp;
recursive(newN, start+1);
}
}
}
Find more posts here.
Cheers & Chao!