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]
]
public class Permutations {
public List<List<Integer>> permute(List<Integer> nums) {
List<List<Integer>> result = new ArrayList<>();
result.add(new ArrayList<>());
for(int num: nums) {
int sz = result.size();
for(int i = 0; i < sz; ++i) {
List<Integer> old = result.get(i);
for(int j = 0; j <= old.size(); ++j) {
List<Integer> updated = new ArrayList<>(old);
updated.add(j, num);
result.add(updated);
}
}
result.subList(0, sz).clear();
}
return result;
}
public static void main(String[] args) {
Permutations p = new Permutations();
List<List<Integer>> result = p.permute(Arrays.asList(1, 2, 3));
System.out.println(result);
}
}
Time complexity: O(n * n!) = O(0! + 1! + 2! + 3! + ...n!)
Iterative: staring with an empty array, { { } }
Adding number 1, { { } } ->{ { 1 } }
Adding number 2, { { 1 } } ->{ { 2 , 1 }, { 1, 2 } }
Adding number 3: { { 2, 1 }, { 1, 2 } } -> { {3, 2, 1}, {2, 3, 1}, {2, 1, 3}, {3, 1, 2}, {1, 3, 2}, {1, 2, 3}}
Taken-out: start with something small, build the solution based on smaller inputs.
Recursive: backtracking, swapping elements to get new array
1. {1, 2, 3} swap the first element with the rest, i = 0
2. After 1 swapped with itsself, {1, 2, 3}, swap the 2nd element with the rest, pos = 1
3. After 2 swapped with itselft, {1, 2, 3}, swap the 3rd element with the rest, pos = 2
4. After 3 swapped with iteself, {1, 2, 3}, you can either return here when pos == nums.size() or pos > nums.size(), result.add(new ArrayList<>(nums)), as base case. {{1, 2, 3}}
5. Back to step 3, 2 swapped with 3, {1, 3, 2}, swap the 3rd element with the rest, pos = 2
6. After 2 swapped with iteself, {1, 3, 2}. { {1, 2, 3}, {1, 3, 2} }
7. Backtracked to step 3, after the subcall which swapped 2 and 3, in order to return the nums to previous state before the subcall, we need to swap the elemtns back.
public class Permutations {
private void permuteHelper(int pos, List<Integer> nums, List<List<Integer>> result) {
int len = nums.size();
if(pos == len-1) {
result.add(new ArrayList<>(nums));
return;
}
for(int i = pos; i < len; ++i) {
Collections.swap(nums, pos, i);
permuteHelper(pos+1, nums, result);
Collections.swap(nums, pos, i);
}
}
public List<List<Integer>> permute(List<Integer> nums) {
List<List<Integer>> result = new ArrayList<>();
permuteHelper(0, nums, result);
return result;
}
public static void main(String[] args) {
Permutations p = new Permutations();
List<List<Integer>> result = p.permute(Arrays.asList(1, 2, 3));
System.out.println(result);
}
}