算法日记day 26（回溯之子集2|非递减子序列|全排列）

一、子集2

题目：

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

思路：

与之前的子集不同的是，这个集合中可能会存在重复元素的子集，因此需要进行去重操作，在树形结构中主要的去重在于树层的去重

代码：

class Solution {

    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 如果数组长度为0，直接返回空集
        if (nums.length == 0) {
            result.add(path); // 添加空集
            return result;
        }

        Arrays.sort(nums); // 先排序数组
        used = new boolean[nums.length]; // 初始化used数组
        subsets(nums, 0); // 生成子集
        return result;
    }

    private void subsets(int[] nums, int startIndex) {
        // 每次递归开始时，将当前路径加入结果集
        result.add(new ArrayList<>(path));

        // 从startIndex开始遍历nums数组
        for (int i = startIndex; i < nums.length; i++) {
            //去重操作，如果当前元素与前一个元素相同，且前一个元素未被使用，则跳过
            if (i > startIndex && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }

            // 添加当前元素到路径中
            path.add(nums[i]);
            //当前元素已经被使用过
            used[i] = true;

            // 递归处理下一个元素
            subsets(nums, i + 1);

            // 回溯，撤销选择
            path.removeLast();
            //path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

1. subsetsWithDup 方法注释：

   • if (nums.length == 0): 如果数组为空，直接返回包含空集的结果。
   • Arrays.sort(nums): 对数组进行排序，为后续去重处理做准备。
   • used = new boolean[nums.length]: 初始化 used 数组，用于标记每个元素是否已经被选择过。
   • subsets(nums, 0): 调用递归方法开始生成子集。

2. subsets 方法注释：

   • result.add(new ArrayList<>(path)): 每次递归开始时，将当前路径加入结果集。
   • 循环遍历 nums 数组，从 startIndex 开始。
   • if (i > startIndex && nums[i] == nums[i - 1] && !used[i - 1]): 如果当前元素与前一个元素相同，并且前一个元素未被使用，则跳过，确保不重复生成相同的子集。
   • path.add(nums[i]): 将当前元素加入路径中，标记为已使用。
   • subsets(nums, i + 1): 递归处理下一个元素。
   • path.remove(path.size() - 1): 回溯，撤销当前选择。
   • used[i] = false: 标记当前元素为未使用。

二、非递减子序列

题目：

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

输入：nums = [4,4,3,2,1]
输出：[[4,4]]

思路：

由于数组中存在重复元素，且必须返回至少两个元素的序列，因此对存入的数组需两个以上才可以转存至结果数组中，且去重操作时，若是将对应的整数数组进行排序，可以会造成输出结果的不准确，因此不能对元素的顺序进行修改

代码：

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 存储所有符合条件的子序列的列表
    LinkedList<Integer> path = new LinkedList<>(); // 当前正在构建的子序列

    // 主函数，找出数组中所有的递增子序列
    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums, 0); // 从数组的第一个元素开始进行回溯
        return result; // 返回所有找到的子序列列表
    }

    // 回溯函数，递归找出所有递增子序列
    public void backtracking(int[] nums, int startIndex) {
        if (path.size() >= 2) { // 如果当前路径长度至少为2，将其加入结果列表
            result.add(new ArrayList<>(path));
        }

        HashSet<Integer> hash = new HashSet<>(); // 使用 HashSet 来记录当前递归层级已经使用过的元素

        for (int i = startIndex; i < nums.length; i++) {
            // 跳过违反递增顺序或已经使用过的元素
            if (!path.isEmpty() && path.getLast() > nums[i] || hash.contains(nums[i])) {
                continue;
            }

            hash.add(nums[i]); // 标记 nums[i] 已经使用
            path.add(nums[i]); // 将 nums[i] 加入当前子序列

            // 递归回溯，从下一个索引开始
            backtracking(nums, i + 1);

            path.removeLast(); // 回溯：从当前子序列移除 nums[i]
        }
    }

}

1. 初始化:

   • List<List<Integer>> result = new ArrayList<>();: 初始化 result 列表，用于存储所有符合条件的子序列。
   • LinkedList<Integer> path = new LinkedList<>();: 初始化 path 链表，用于存储当前正在构建的子序列。

2. findSubsequences 方法:

   • backtracking(nums, 0);: 从数组 nums 的起始位置开始进行回溯。
   • return result;: 回溯完成后返回所有找到的子序列列表。

3. backtracking 方法:

   • 基本条件:

     • if (path.size() >= 2) { ... }: 如果当前路径 path 的长度至少为2，则将其加入 result 列表中。

   • 回溯逻辑:

     • HashSet<Integer> hash = new HashSet<>();: 使用 HashSet 来记录当前递归层级已经使用过的元素，避免重复。

     • 遍历 nums 数组:

       • for (int i = startIndex; i < nums.length; i++) { ... }: 从 startIndex 开始遍历 nums 数组。

     • 跳过条件:

       • if (!path.isEmpty() && path.getLast() > nums[i] || hash.contains(nums[i])) { continue; }: 跳过违反递增顺序或已经使用过的元素。

     • 递归步骤:

       • hash.add(nums[i]);: 标记 nums[i] 已经在当前递归层级中使用。
       • path.add(nums[i]);: 将 nums[i] 加入当前正在构建的子序列 path 中。
       • backtracking(nums, i + 1);: 递归调用 backtracking，从下一个索引位置开始继续查找。

     • 回溯操作:

       • path.removeLast();: 回溯操作，从当前子序列 path 中移除最后一个元素 nums[i]。 

在去重逻辑中

if (!path.isEmpty() && path.getLast() > nums[i] || hash.contains(nums[i])) {
    continue;
}

1. !path.isEmpty() && path.getLast() > nums[i]:

   • !path.isEmpty(): 检查当前路径 path 是否为空，即当前正在构建的子序列是否已经有元素。
   • path.getLast() > nums[i]: 检查当前正在构建的子序列的最后一个元素是否大于当前考虑的 nums[i]。
   • 如果以上两个条件满足，则说明 nums[i] 所在的路径不满足递增要求（因为当前路径的最后一个元素大于 nums[i]），因此应该跳过当前的 nums[i]。

2. || hash.contains(nums[i]):

   • hash.contains(nums[i]): 使用 HashSet hash 来记录当前递归层级已经使用过的元素。
   • 如果 hash 中已经包含了 nums[i]，则说明 nums[i] 已经在当前路径中出现过，因此也应该跳过当前的 nums[i]。

3. continue;:

   • 如果以上任何一个条件满足，即当前 nums[i] 不符合递增子序列的要求（要么不大于当前路径的最后一个元素，要么已经在当前路径中出现过），则使用 continue; 跳过当前循环，继续考虑下一个 nums[i]。

三、全排列 

题目：

给定一个不含重复数字的数组 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]]

思路：

由于题目要求是输出所有的排列情况，并非组合，因此在循环时必须每个元素都进行标记，直到全部元素都标记完毕时才能输出至结果数组中

代码：

List<List<Integer>> result = new ArrayList<>(); // 用于存储所有排列的结果
LinkedList<Integer> path = new LinkedList<>(); // 当前正在构建的排列
boolean[] used; // 标记每个元素是否已被使用过

public List<List<Integer>> permute(int[] nums) {
    if (nums.length == 0) {
        return result; // 如果数组为空，直接返回空结果列表
    }
    used = new boolean[nums.length]; // 初始化 used 数组
    backtracking(nums); // 开始回溯
    return result; // 返回所有排列的结果
}

public void backtracking(int[] nums) {
    if (path.size() == nums.length) { // 如果当前排列长度等于 nums 的长度
        result.add(new ArrayList<>(path)); // 将当前排列加入结果列表
        return; // 结束当前递归
    }
    for (int i = 0; i < nums.length; i++) { // 尝试每个元素作为下一个排列元素
        if (used[i]) { // 如果元素已被使用过
            continue; // 跳过当前循环
        }
        used[i] = true; // 标记元素为已使用
        path.add(nums[i]); // 将元素加入当前排列
        backtracking(nums); // 递归进入下一层决策树
        used[i] = false; // 回溯，撤销选择
        path.removeLast(); // 移除当前排列的最后一个元素
    }
}

1. 变量定义：

   • List<List<Integer>> result = new ArrayList<>();: 用于存储所有符合条件的排列的列表。
   • LinkedList<Integer> path = new LinkedList<>();: 当前正在构建的排列。
   • boolean[] used;: 用于标记数组 nums 中的元素是否已经被使用过。

2. permute 方法：

   • public List<List<Integer>> permute(int[] nums) { ... }
   • 首先检查如果 nums 的长度为0，则直接返回 result，因为没有元素可以排列。
   • 初始化 used 数组，长度与 nums 相同，用来标记每个元素的使用情况。
   • 调用 backtracking(nums) 开始进行排列的回溯过程。
   • 返回 result 列表，其中包含所有的排列结果。

3. backtracking 方法：

   • public void backtracking(int[] nums) { ... }
   • 基本结束条件：当 path 的长度等于 nums 的长度时，说明已经构建出一个完整的排列，将其加入 result 中。
   • 循环尝试每个元素：
     • 使用 for 循环遍历 nums 数组。
     • 检查 used[i]，如果为 true，说明当前元素已经被使用过，跳过当前循环。
     • 如果 used[i] 为 false，则将 nums[i] 加入 path 中，并标记 used[i] 为 true，表示当前元素已经被使用。
     • 递归调用 backtracking(nums)，继续构建下一个元素的排列。
     • 回溯步骤：将 used[i] 设为 false，表示当前元素未被使用，从 path 中移除最后一个元素，继续尝试其他可能性。

四、全排列2

题目：

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路：

与全排列1类似，但是由于数组中有重复元素，因此需要考虑在树层上的去重问题，判断前后元素是否一致且是否已经标记使用过，如果是，则跳过，否则加入结果中

代码：

class Solution {
    List<List<Integer>> result = new ArrayList<>(); // 存储所有唯一排列的结果
    LinkedList<Integer> path = new LinkedList<>(); // 当前正在生成的排列
    boolean[] used; // 记录每个元素是否已经被使用过

    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums.length == 0) {
            return result;
        }

        Arrays.sort(nums); // 对数组进行排序，确保相同元素相邻
        used = new boolean[nums.length]; // 初始化used数组，长度与nums相同，初始值均为false
        backtracking(nums); // 调用回溯算法生成排列
        return result;
    }

    public void backtracking(int[] nums) {
        if (path.size() == nums.length) { // 如果当前排列长度等于nums的长度，说明找到了一个全排列
            result.add(new ArrayList<>(path)); // 将当前排列加入结果集合中
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (used[i]) { // 如果当前元素已经被使用过，跳过
                continue;
            }

            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                // 如果当前元素与前一个元素相同，并且前一个元素未被使用，则跳过，避免生成重复的排列
                continue;
            }

            used[i] = true; // 标记当前元素已被使用
            path.add(nums[i]); // 将当前元素加入当前排列
            backtracking(nums); // 递归生成下一个位置的元素
            used[i] = false; // 恢复当前元素为未使用
            path.removeLast(); // 移除当前排列的最后一个元素，回溯到上一个状态
        }
    }
}

1. 全局变量声明：

   • List<List<Integer>> result = new ArrayList<>();：存储所有唯一排列的结果。
   • LinkedList<Integer> path = new LinkedList<>();：当前正在生成的排列。
   • boolean[] used;：记录每个元素是否已经被使用过的标志数组。

2. 函数 permuteUnique：

   • if (nums.length == 0)：如果输入数组为空，直接返回 result。
   • Arrays.sort(nums);：对 nums 进行排序，确保相同的元素相邻。
   • used = new boolean[nums.length];：初始化 used 数组，长度与 nums 相同，初始值为 false。
   • backtracking(nums);：调用回溯算法开始生成排列。

3. 函数 backtracking：

   • if (path.size() == nums.length)：如果当前排列长度等于 nums 的长度，将当前排列加入 result 中。
   • for (int i = 0; i < nums.length; i++)：遍历 nums 数组中的每个元素。
     • if (used[i]) continue;：如果当前元素已经被使用过，跳过。
     • if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;： 如果当前元素与前一个元素相同，并且前一个元素未被使用，则跳过，以避免生成重复的排列。
     • used[i] = true;：标记当前元素为已使用。
     • path.add(nums[i]);：将当前元素加入 path 中。
     • backtracking(nums);：递归生成下一个位置的元素。
     • used[i] = false;：恢复当前元素为未使用。
     • path.removeLast();：移除 path 中的最后一个元素，进行回溯。

今天的学习就到这里