题目:给定一个不含重复数字的数组 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]]
思路:dfs
public class ABC {
public static void main(String[] args) {
int[] arr = {1,2,3};
List<List<Integer>> res = permute(arr);
System.out.println(res);
}
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
if (nums == null) {
return ans;
}
int index = 0;
dfs(ans, nums, index);
return ans;
}
private static void dfs(List<List<Integer>> ans, int[] chars, int index) {
// 1.终止条件
// 2.小集合加入大集合
if (index == chars.length) {
String s = Arrays.toString(chars);
String[] split = s.replaceAll(" ", "").replace("[", "")
.replace("]", "").split(",");
List<Integer> path = Arrays.stream(split).filter(str -> !Objects.equals(str, ""))
.map(Integer::valueOf).collect(Collectors.toList());
ans.add(path);
return;
}
// 3.元素加入小集合
for (int i = index; i < chars.length; i++) {
swap(chars, i, index);
// 4.递归
dfs(ans, chars, index + 1);
// 5.回溯
swap(chars, i, index);
}
}
private static void swap(int[] chars, int i, int j) {
int temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}