一次一粒沙,一次一件事。 ——《人性的优点》
给定一个不含重复数字的数组 nums ,返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入:nums = [1,2,3]
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
输入:nums = [0,1]
输出:[[0,1],[1,0]]
输入:nums = [1]
输出:[[1]]
1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同
回溯万能模板:
void backtracking(/* 所需参数(访问标记, 中间存储, 最终存储, 原始数据)*/) {
// TODO 自动生成的方法存根
if(/*终止条件*/) {
//一种情况,加入最终存储
return; //返回
}
for(/*对现有条件进行罗列*/) {
if(/*判断是否合理,或者是否已访问*/) {
continue;//跳过
}
//将该元素加入中间存储(修改条件)
//标位已访问
backtracking(/*参数*/); //递归调用自身
//将该元素从中间存储删除(条件复位,即 :回溯)
//标记为未访问
}
}
本题注意点:ArrayList是一个引用类型,因此每次都要new一个再加入到list中
import java.util.ArrayList;
import java.util.List;
public class arrangement {
public static void main(String[] args) {
// TODO 自动生成的方法存根
int [] nums = {1, 2, 3};
System.out.println(permute(nums));
}
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> alarr = new ArrayList<>();
List<Integer> midarr = new ArrayList<>();
boolean [] hasVisited = new boolean [nums.length];
if(nums == null || nums.length == 0) {
return alarr;
}
backtracking(hasVisited, midarr, alarr, nums);
return alarr;
}
private static void backtracking(boolean[] hasVisited, List<Integer> midarr, List<List<Integer>> alarr, int[] nums) {
// TODO 自动生成的方法存根
if(midarr.size() == hasVisited.length) {
alarr.add(new ArrayList<>(midarr));//重新构造一个 List
return;
}
int n = hasVisited.length;
for(int i = 0; i < n; i++) {
if(hasVisited[i]) {
continue;
}
midarr.add(nums[i]);
hasVisited[i] = true;
backtracking(hasVisited, midarr, alarr, nums);
midarr.remove(midarr.size() - 1);
hasVisited[i] = false;
}
}
}
257. 二叉树的所有路径
79. 单词搜索
93. 复原 IP 地址
17. 电话号码的字母组合
47. 全排列 II
题目来源:力扣