Given 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
| [
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
|
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
| class Solution {
public List<List<Integer>> permute(int[] nums) {
if(nums.length == 0) return null;
List<List<Integer>> ans = new ArrayList<List<Integer>>();
boolean[] used = new boolean[nums.length];
ArrayList<Integer> t = new ArrayList<Integer>();
dfs(ans, nums, t, used);
return ans;
}
public void dfs(List<List<Integer>> ans, int[] nums, ArrayList<Integer> t, boolean[] used){
if(t.size() == nums.length){
ans.add(new ArrayList(t));
return ;
}
for(int i=0; i<nums.length; i++){
if(!used[i]){
used[i] = true;
t.add(nums[i]);
dfs(ans, nums, t, used);
used[i] = false;
t.remove(t.size()-1);
}
}
}
}
|
- 使用一个数组used来保存当前已经加入数组t中的元素。
- 使用dfs的方法，找到一个可行解后，回溯，更换另一个解。
