LeetCode - Permutations
Problem description
Given a collection of distinct integers, return all possible permutations.
Example:
1
2
3
4
5
6
7
8
9
10
Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
Analysis
This is a typical backtrack problem. Here’s the code:
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
class Solution {
public List<List<Integer>> permute(int[] nums) {
boolean[] used = new boolean[nums.length];
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, res, new ArrayList<>(), used);
return res;
}
void backtrack(int[] nums, List<List<Integer>> res, List<Integer> list, boolean[] used){
if (list.size() == nums.length){
res.add(new ArrayList<>(list));
return;
}
for (int i = 0; i< nums.length; i++){
if (!used[i]){
list.add(nums[i]);
used[i] = true;
backtrack(nums, res, list, used);
used[i] = false;
list.remove(list.size() - 1);
}
}
}
}