46. 全排列
自己解法
这个题的思路比较简单，就是经典的回溯法，但是写起来并没有那么的得心应手，主要是对于还可以使用的元素的处理不是特别清晰，最开始是可使用元素也用了回溯的操作，这样发现循环里面会存在增加元素，而继续进行的情况，把这个地方改成每次新维护数组以后就可以了。
class Solution {
List<List<Integer>> output = new ArrayList<>(16);
List<Integer> res = new ArrayList<>(16);
int count;
public List<List<Integer>> permute(int[] nums) {
if (nums.length == 0) {
return output;
}
count = nums.length;
List<Integer> remainNums = Arrays.stream(nums)
.boxed()
.collect(Collectors.toList());
dfs(remainNums);
return output;
}
public void dfs(List<Integer> remainNums) {
if (res.size() == count) {
output.add(new ArrayList<Integer>(res));
return;
}
for (int i = 0; i < remainNums.size(); i++) {
int a = remainNums.get(i);
List<Integer> remainList = new ArrayList<Integer>(remainNums);
res.add(a);
remainList.remove(i);
dfs(remainList);
res.remove(res.size() - 1);
}
}
}
官方解法
首先解法思路都是一样的，这种是用了个boolean[] used来维护哪些下标是已经访问过的，在回溯的过程中,置used[i]为false，来重置，这样处理整体更协调一些。
import java.util.ArrayList;
import java.util.List;
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;
}
boolean[] used = new boolean[len];
List<Integer> path = new ArrayList<>();
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth,
List<Integer> path, boolean[] used,
List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<Integer>(path));
return;
}
for (int i = 0; i < len; i++) {
if (!used[i]) {
path.add(nums[i]);
used[i] = true;
dfs(nums, len, depth + 1, path, used, res);
// 注意：这里是状态重置，是从深层结点回到浅层结点的过程，代码在形式上和递归之前是对称的
used[i] = false;
path.remove(path.size() - 1);
}
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Solution solution = new Solution();
List<List<Integer>> lists = solution.permute(nums);
System.out.println(lists);
}
}
