05 August 2008
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]
]
给一个distinct数字元素的集合，返回所有可能的组合，这道题依然用Backtracking的模板来做，注意这不是最快的办法。
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
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if (nums == null || nums.length == 0) {
return results;
}
dfs(nums, results, new ArrayList<>());
return results;
}
private void dfs(int[] nums, List<List<Integer>> results, List<Integer> oneResult) {
if (oneResult.size() == nums.length) {
results.add(new ArrayList<>(oneResult));
return;
}
for (int num : nums) { // 当前数取了后应该从index = 0从头开始
if (oneResult.contains(num)) {
continue;
}
oneResult.add(num);
dfs(nums, results, oneResult); //oneResult已经变化
oneResult.remove(oneResult.size() - 1);
}
}
}