友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入：nums = [0,1] 输出：[[0,1],[1,0]]
示例 3：
输入：nums = [1] 输出：[[1]]
提示：
-
1 <= nums.length <= 6 -
-10 <= nums[i] <= 10 -
nums中的所有整数 互不相同
思路分析
-
一刷
-
二刷
-
三刷
-
四刷（回溯）
-
五刷（子集）
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
/**
* Runtime: 5 ms, faster than 8.40% of Java online submissions for Permutations.
*
* Memory Usage: 45.3 MB, less than 5.68% of Java online submissions for Permutations.
*
* Copy from: https://leetcode.com/problems/permutations/discuss/18239/A-general-approach-to-backtracking-questions-in-Java-(Subsets-Permutations-Combination-Sum-Palindrome-Partioning)[A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partioning) - LeetCode Discuss]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-24 12:35
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new LinkedList<>();
backtrack(nums, result, new ArrayList<Integer>());
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result, ArrayList<Integer> path) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
} else {
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
if (path.contains(num)) {
continue;
}
path.add(num);
backtrack(nums, result, path);
path.remove(path.size() - 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
27
28
29
30
31
32
33
34
/**
* 参考《算法小抄》的参数，自己实现的
*
* @author D瓜哥 · https://www.diguage.com
* @since 2024-06-28 22:30
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, result, path, used);
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result,
List<Integer> path, boolean[] used) {
if (nums == null || nums.length == 0) {
return;
}
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
backtrack(nums, result, path, used);
path.remove(path.size() - 1);
used[i] = false;
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-09-18 22:11:50
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, result, used, new ArrayList(nums.length));
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result,
boolean[] used, List<Integer> path) {
if (path.size() == nums.length) {
result.add(new ArrayList(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
used[i] = true;
path.add(nums[i]);
backtrack(nums, result, used, path);
path.remove(path.size() - 1);
used[i] = false;
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-06 16:50
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, result, new ArrayList<>(), new boolean[nums.length]);
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result,
List<Integer> path, boolean[] used) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
// 选择
used[i] = true;
path.add(nums[i]);
backtrack(nums, result, path, used);
// 撤销
path.removeLast();
used[i] = false;
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-04-10 17:22:39
*/
public List<List<Integer>> permute(int[] nums) {
Queue<List<Integer>> result = new LinkedList<>();
result.offer(new ArrayList<>(List.of(nums[0])));
for (int i = 1; i < nums.length; i++) {
int num = nums[i];
int size = result.size();
for (int j = 0; j < size; j++) {
List<Integer> tmp = result.poll();
for (int k = 0; k <= tmp.size(); k++) {
List<Integer> adding = new ArrayList<>(tmp);
if (k == tmp.size()) {
adding.add(num);
} else {
adding.add(k, num);
}
result.offer(adding);
}
}
}
return new ArrayList<>(result);
}