1 今日打卡
递增子序列 491. 非递减子序列 – 力扣（LeetCode）
全排列 46. 全排列 – 力扣（LeetCode）
全排列2 47. 全排列 II – 力扣（LeetCode）
2 递增子序列
2.1 思路
只要path长度≥2 就收集，因为递增子序列可在任意位置结束（如[4,6]是合法结果，无需等到选 7）,因此在收集的时候不要写return,因为要继续向下遍历，直到for循环结束。 哈希集合used定义在递归方法内，仅作用于当前层，不同层的used相互独立，保证 “不同层可重复选同一数字（如[4,7,7]），同一层不可重复选（避免[4,7]重复出现）。在寻找递增子序列时，同一层递归中如果选择了相同的数字，会生成重复的子序列，而我们要找的是 “不重复的递增子序列”，所以必须在同一层中避免选重复的数。
用 nums = [4, 6, 7, 7] 来举例，聚焦最容易出问题的 “同一层重复选 7” 的场景： 没有 hs（会生成重复子序列）的情况： 假设去掉 hs 相关的代码，只保留 “递增” 的剪枝条件，看执行过程： 第一层递归（startIndex=0）选 4 → path=[4]，进入第二层（startIndex=1）。 第二层递归（startIndex=1）： i=2（nums [i]=7）：path=[4,7] → 加入 result。 i=3（nums [i]=7）：path 最后一个数是 4 ≤7，没有 hs 限制 → 会再次选 7，path=[4,7] → 又一次加入 result。 → 最终 result 中会出现两个 [4,7]，这是重复的，不符合要求。
第三层选 7 后，hs={7}，但第二层的 hs 不会受影响，这保证了 “不同层可以选相同的数（比如 [4,7,7] 是合法的），但同一层不能选相同的数”。
2.2 实现代码
class Solution {
// 最终结果集：存储所有符合条件的递增子序列
List<List<Integer>> result = new ArrayList<>();
// 路径：记录当前递归中正在构建的子序列（回溯的核心载体）
List<Integer> path = new ArrayList<>();
/**
* 主方法：入口，调用回溯函数并返回结果
* @param nums 输入的整数数组
* @return 所有长度≥2的递增子序列
*/
public List<List<Integer>> findSubsequences(int[] nums) {
// 从数组下标0开始回溯，保证子序列的相对顺序
backTracking(nums, 0);
return result;
}
/**
* 回溯核心方法
* @param nums 输入数组
* @param startIndex 当前层递归的起始遍历下标（避免回头选元素，保证相对顺序）
*/
private void backTracking(int[] nums, int startIndex) {
// 收集结果：只要当前路径长度≥2，就加入结果集（无需等到递归终止）
// 注意：必须new ArrayList<>(path)，否则path回溯修改会影响result中的元素
if (path.size() >= 2) {
result.add(new ArrayList<>(path));
}
// 分层去重：哈希集合记录当前层已选过的数字，避免同一层选重复数字生成重复子序列
HashSet<Integer> used = new HashSet<>();
// 从startIndex开始遍历，保证子序列元素的相对顺序
for (int i = startIndex; i < nums.length; i++) {
// 剪枝条件（二选一触发则跳过当前元素）：
// 1. 路径非空时，当前元素 < 路径最后一个元素（不满足递增）
// 2. 当前层已经选过该元素（去重）
if ((!path.isEmpty() && path.get(path.size() – 1) > nums[i]) || used.contains(nums[i])) {
continue;
}
// 标记当前层已选过该元素，后续同层遍历不再选
used.add(nums[i]);
// 将当前元素加入路径，构建子序列
path.add(nums[i]);
// 递归：下一层从i+1开始（不能选当前元素及之前的元素）
backTracking(nums, i + 1);
// 回溯：移除路径最后一个元素，尝试同层下一个元素
path.remove(path.size() – 1);
}
}
// 测试示例
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {4, 6, 7, 7};
List<List<Integer>> res = solution.findSubsequences(nums);
// 输出结果：[[4,6], [4,6,7], [4,6,7,7], [4,7], [4,7,7], [6,7], [6,7,7], [7,7]]
System.out.println(res);
}
}
3 全排列
3.1 思路
每一层递归中，从头遍历整个数组，排列不要求元素的相对顺序，比如选完 1 后，下一个可以选 2 或 3；选完 2 后，下一个可以选 1 或 3。遇到used[i]=true的元素直接跳过（该元素已被选入当前排列，不能重复选）。
不像前面系列的问题一样需要startIndex，因为这是全排列问题。
3.2 实现代码
class Solution {
// 最终结果集：存储所有完整的排列组合
List<List<Integer>> res = new ArrayList<>();
// 路径：记录当前递归中正在构建的排列（用LinkedList便于尾部增删）
LinkedList<Integer> path = new LinkedList<>();
/**
* 主方法：入口，初始化标记数组并调用回溯函数
* @param nums 输入的整数数组（无重复元素）
* @return 数组的所有全排列
*/
public List<List<Integer>> permute(int[] nums) {
// 标记数组：记录每个元素是否已被选入path，长度与nums一致
boolean[] used = new boolean[nums.length];
backtracking(nums, used);
return res;
}
/**
* 回溯核心方法
* @param nums 输入数组
* @param used 标记数组：used[i]=true 表示nums[i]已被选入当前排列
*/
public void backtracking(int[] nums, boolean[] used) {
// 终止条件：path长度等于数组长度，说明已生成一个完整排列
if (path.size() == nums.length) {
// 拷贝path到新列表，避免后续回溯修改结果集
res.add(new ArrayList<>(path));
return; // 终止当前递归，返回上一层
}
// 遍历数组所有元素（全排列需从头遍历，而非从startIndex，因为要选所有未用元素）
for (int i = 0; i < nums.length; i++) {
// 剪枝：跳过已被选入当前排列的元素
if (used[i] == true) {
continue;
}
// 标记当前元素已使用，避免同一排列中重复选择
used[i] = true;
// 将当前元素加入路径，构建排列
path.add(nums[i]);
// 递归：继续选择下一个未使用的元素
backtracking(nums, used);
// 回溯1：移除路径最后一个元素，尝试下一个可能的元素
path.remove(path.size() – 1);
// 回溯2：取消当前元素的使用标记，让后续层可以重新选择
used[i] = false;
}
}
4 全排列Ⅱ
4.1 思路
排序预处理：先对数组排序，让重复元素相邻 —— 这是后续 “识别重复值、精准去重” 的前提； 树层去重过滤重复排列：在遍历过程中，通过used[i-1] == false判断 “同一递归层（树层）的重复值已被使用”，跳过该元素，避免生成重复的排列结果。used[i-1] == false表明前一个重复元素已遍历完并回溯，说明 “同一层已用过该重复值”，跳过当前元素避免重复排列。
4.2 实现代码
class Solution {
// 最终结果集：存储所有不重复的全排列
List<List<Integer>> res = new ArrayList<>();
// 路径：记录当前递归中正在构建的排列（LinkedList便于尾部增删）
LinkedList<Integer> path = new LinkedList<>();
/**
* 主方法：入口，初始化并调用回溯函数
* @param nums 含重复元素的整数数组
* @return 所有不重复的全排列
*/
public List<List<Integer>> permuteUnique(int[] nums) {
// 关键预处理：排序让重复元素相邻，为树层去重做准备
Arrays.sort(nums);
// 标记数组：used[i]=true 表示nums[i]已被选入当前排列（树枝）
boolean[] used = new boolean[nums.length];
backtracking(nums, used);
return res;
}
/**
* 回溯核心方法
* @param nums 输入数组
* @param used 标记数组：记录元素是否被选入当前排列
*/
public void backtracking(int[] nums, boolean[] used) {
// 终止条件：path长度等于数组长度，说明生成了一个完整排列
if (path.size() == nums.length) {
// 拷贝path到新列表，避免后续回溯修改结果集
res.add(new ArrayList<>(path));
return;
}
// 遍历所有元素（全排列需从头遍历，而非startIndex）
for (int i = 0; i < nums.length; i++) {
// 核心去重：跳过同一树层的重复元素
// 条件拆解：
// 1. i>0：避免数组越界
// 2. nums[i-1] == nums[i]：当前元素和前一个元素重复
// 3. used[i-1] == false：前一个重复元素已回溯（说明在同一树层被用过）
if (i > 0 && nums[i – 1] == nums[i] && used[i – 1] == false) {
continue;
}
// 基础剪枝：跳过同一排列（树枝）中已选过的元素
if (used[i] == true) {
continue;
}
// 选择当前元素：标记为已使用，加入路径
used[i] = true;
path.add(nums[i]);
// 递归下探：继续构建排列的下一个元素
backtracking(nums, used);
// 回溯1：移除路径最后一个元素，回到上一层状态
path.remove(path.size() – 1);
// 回溯2：取消元素的使用标记，允许后续层重新选择
used[i] = false;
}
}
