盒子
盒子
文章目录
  1. 46. 全排列

46_全排列_leetcode

46. 全排列

给定一个没有重复数字的序列,返回其所有可能的全排列。

示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

题解: 回溯算法,Set用于判断数字是否已经用于排列,Stack先进后出特性 + 递归实现回溯

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
public class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}

Set<Integer> used = new HashSet<>();
Stack<Integer> stack = new Stack<>();
backtrack(nums, 0, len, used, stack, res);
return res;
}

private void backtrack(int[] nums, int depth, int len, Set<Integer> used, Stack<Integer> stack, List<List<Integer>> res) {
if (depth == nums.length) { // 全部数字已排列完,加入结果集
res.add(new ArrayList<>(stack));
return ;
}
for (int i = 0; i < len; i++) {
if (!used.contains(i)) { // 排列之前未排列的数字
used.add(i);
stack.push(nums[i]);
// 递归求解
backtrack(nums, depth + 1, len, used, stack, res);
stack.pop();
used.remove(i);
}
}
}
}

AC传送门leetcode

支持一下
扫一扫,支持沈健
  • 微信扫一扫
  • 支付宝扫一扫