2025年- H68-Lc176--46.全排列(回溯,组合）--Java版

1.题目描述

2.思路

（1）终止条件：当path.size()==nums.size(）说明要到收获的结果了（也就是叶子节点）。
（2）思路
使用一个临时列表 cur 表示当前构造中的排列；

每次递归遍历 nums 中还未使用的元素；

达到终止条件后将 cur 加入结果集中；

用回溯法（递归 + 回退）尝试所有可能。
(3)cur.remove(cur.size()-1)
假设 cur 列表目前是 [1, 2, 3]，此时调用 cur.remove(cur.size() - 1) 后：

cur.size() = 3

cur.size() - 1 = 2

所以 cur.remove(2) 就是移除索引为 2 的元素，即移除 3，此时 cur 变成 [1, 2]。

3.代码实现

class Solution {public List<List<Integer>> permute(int[] nums) {//res：用于保存所有的排列结果。List<List<Integer>> res=new ArrayList<>();//cur：当前正在构造的排列序列。List<Integer> cur=new ArrayList<>();//调用回溯函数开始递归构造所有排列。backtracking(res,cur,nums);//返回最终的所有排列结果。return res;}private static void backtracking(List<List<Integer>> res,List<Integer> cur,int[] nums){//终止条件,排序序列的长度等于数组长度if(cur.size()==nums.length){res.add(new ArrayList<>(cur));}//定义回溯方法，递归地构造排列。for(int i=0;i<nums.length;i++){if(!cur.contains(nums[i])){//遍历 nums 中的所有元素，尝试每个元素加入当前排列 cur。// 如果当前元素还未被使用（即不在当前排列 cur 中），则继续处理。防止重复使用同一个元素。cur.add(nums[i]);//选择这个元素，加入到当前排列中。backtracking(res,cur,nums);//撤销选择（回溯）：将当前选择的元素移除，为下一轮尝试其他可能性做好准备。cur.remove(cur.size()-1);}}//遍历 nums 中的所有元素，尝试每个元素加入当前排列 cur。}
}