-
Notifications
You must be signed in to change notification settings - Fork 1
/
Permutations.java
93 lines (77 loc) · 2.03 KB
/
Permutations.java
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
package leetcode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
/**
* https://leetcode.com/problems/permutations/
* <p>
* https://leetcode-cn.com/problems/permutations/solution/quan-pai-lie-by-leetcode-solution-2/
*/
public class Permutations {
/**
* return permute(nums, 0);
*
* @param nums
* @param start
* @return
* @deprecated
*/
@Deprecated
public List<List<Integer>> permute(int[] nums, int start) {
if (start == nums.length - 1) {
return Collections.singletonList(Collections.singletonList(nums[start]));
}
List<List<Integer>> ret = new ArrayList<>();
for (List<Integer> cur : permute(nums, start + 1)) {
for (int i = 0; i <= cur.size(); ++i) {
List<Integer> l = new ArrayList<>(cur);
l.add(i, nums[start]);
ret.add(l);
}
}
return ret;
}
// --------------------------------------------------------------
// dfs
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) {
return Collections.emptyList();
}
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> stack = new ArrayDeque<>();
boolean[] used = new boolean[nums.length];
dfs(nums, 0, stack, used, res);
return res;
}
/**
* @param nums 数据集合
* @param depth 深度
* @param path 路径
* @param used 使用的数据集合标记
* @param res 结果
*/
private void dfs(int[] nums, int depth, Deque<Integer> path, boolean[] used,
List<List<Integer>> res) {
// 终止条件
if (depth == nums.length) {
res.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
// 当前层逻辑
if (used[i]) {
continue;
}
// 当前层逻辑
path.addLast(nums[i]);
used[i] = true;
// 下探一层
dfs(nums, depth + 1, path, used, res);
// 清理当前层数据
path.removeLast();
used[i] = false;
}
}
}