题目描述
输入一组数字(可能包含重复数字),输出其所有的排列方式。
样例
输入:[1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
算法1
回溯
分享一个比较麻烦但是好理解的思路
- 定义 res 为全局变量,用于收集结果
- path 列表用于记录路径
- visited[i] 表示 nums[i] 有没有被遍历过
- 然后再看 backTracking 中的代码
- 如果 path 的长度等于数组长度,说明数组中数字全部用完,添加至结果集,并返回
- 否则,我们开始分析下一个可以选择的数
- 首先,已经选择过的数,肯定不能再选择了,所以跳过所有 visited[i] == true 的数
- 其次,不能选择重复的数,因为一旦重复,结果集中就会出现重复结果。所以这里使用 HashSet 过滤掉重复的数
- 然后就是回溯的之后,要将 path 和 visited 数组的状态恢复到之前状态
Java 代码
class Solution {
private List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permutation(int[] nums) {
int len = nums.length;
if(len == 0) return new ArrayList<>();
List<Integer> path = new ArrayList<>();
boolean[] visited = new boolean[nums.length];
backTracking(path, nums, visited);
return res;
}
private void backTracking(List<Integer> path, int[] nums, boolean[] visited){
if(path.size() == nums.length) {
res.add(new ArrayList<>(path));
return;
}
Set<Integer> set = new HashSet<>();
for(int i = 0; i < nums.length; i++) {
if(visited[i] || set.contains(nums[i])) continue;
set.add(nums[i]);
path.add(nums[i]);
visited[i] = true;
backTracking(path, nums, visited);
visited[i] = false;
path.remove(path.size() - 1);
}
}
}