day 25 第七章 回溯算法part04

第一题：491.递增子序列

解题思路分析

本题要求找出给定整数数组 nums 中所有不同的递增子序列，且子序列至少有两个元素。可以使用回溯算法来解决这个问题，以下是具体思路：

代码

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        backTracking(nums,0);
        return result;
    }
    private void backTracking(int[] nums,int startIndex){
        if(path.size() >= 2){
            result.add(new ArrayList<>(path));
        }
        HashSet<Integer> hs = new HashSet<>();
        for(int i = startIndex;i < nums.length;i++){
            if(!path.isEmpty() && path.get(path.size() - 1) > nums[i] || hs.contains(nums[i])){
                continue;
            }
            hs.add(nums[i]);
            path.add(nums[i]);
            backTracking(nums,i + 1);
            path.remove(path.size() - 1);
        }
    }
}

第二题：46.全排列

解题思路分析

本题要求返回给定数组 nums（数组中不含重复数字）的所有可能全排列，解题思路主要基于回溯算法，以下是详细说明：

1. 整体框架：
   通过定义 permuteHelper 这个辅助方法进行回溯操作，从空的排列开始，逐步往里面添加元素，尝试所有可能的排列组合情况，将得到的每一种全排列结果添加到最终的 result 列表中。

2. 初始化与辅助数组：
   在 permute 方法中，首先判断如果输入的 nums 数组长度为 0，则直接返回空的 result 列表。然后创建一个布尔类型的数组 used，其长度与 nums 数组长度相同，用于记录 nums 中的每个元素是否已经被使用过，初始时所有元素都标记为未使用（false），接着调用 permuteHelper 方法开始回溯过程。

3. 终止条件判断：
   在 permuteHelper 方法里，当当前构建的排列 path 的长度等于 nums 数组的长度时，意味着已经得到了一种完整的全排列情况，此时将这个 path 的副本（通过 new ArrayList<>(path) 创建副本，避免后续修改影响已添加的结果）添加到 result 列表中，然后直接返回，结束当前这一轮的递归探索。

4. 遍历与选择元素：
   使用 for 循环遍历 nums 数组，对于每一个元素 nums[i]，先检查其对应的 used[i] 是否为 true，如果为 true，说明这个元素已经在当前正在构建的排列中被使用过了，就跳过该元素（通过 continue 语句），去检查下一个元素；若 used[i] 为 false，则表示这个元素还未被使用，可以将其添加到当前的排列 path 中，此时将 used[i] 标记为 true，表示该元素已被选用了。

5. 递归探索与回溯：
   在将元素 nums[i] 添加到 path 中后，接着以这个新的状态递归调用 permuteHelper 方法，继续去探索后续还可以添加哪些元素来构成完整的全排列。当这一层递归调用结束后（也就是以当前添加的这个元素为基础的所有可能排列情况都探索完了），需要进行回溯操作，先将刚添加到 path 中的元素移除（通过 path.removeLast()，因为 path 是 LinkedList，用这个方法方便移除最后一个元素），然后把对应的 used[i] 标记回 false，这样就回到了添加这个元素之前的状态，能够去尝试其他的元素选择，继续探索不同的排列组合情况。

6. 最终结果返回：
   在 permute 主方法中，经过一系列的回溯探索后，result 列表中就收集了所有的全排列情况，最后将其返回。

代码

class Solution {
    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];
        permuteHelper(nums);
        return result;
    }
    private void permuteHelper(int[] nums){
        if(path.size() == nums.length){
            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]);
            permuteHelper(nums);
            path.removeLast();
            used[i] = false;
        }
    }
}

第三题：47.全排列II

解题思路分析

本题要求给定一个可包含重复数字的序列 nums，返回所有不重复的全排列，解题思路依然基于回溯算法，但相较于不包含重复数字求全排列的题目，需要额外处理重复元素的情况，以下是详细说明：

1. 整体框架：
   通过 backTracking 方法进行回溯操作，从空的排列开始，逐步往里面添加元素，尝试所有可能的排列组合情况，将得到的不重复的全排列结果添加到最终的 result 列表中。

2. 初始化与预处理：
   在 permuteUnique 方法中，首先创建一个布尔类型的数组 used，其长度与 nums 数组长度相同，用于记录 nums 中的每个元素是否已经被使用过，初始时通过 Arrays.fill(used, false) 将所有元素都标记为未使用。然后对 nums 数组进行排序（通过 Arrays.sort(nums)），排序的目的是方便后续处理重复元素，使得相同的元素能够相邻，便于识别和去重，之后调用 backTracking 方法开始回溯过程。

3. 终止条件判断：
   在 backTracking 方法里，当当前构建的排列 path 的长度等于 nums 数组的长度时，意味着已经得到了一种完整的全排列情况，此时将这个 path 的副本（通过 new ArrayList<>(path) 创建副本，避免后续修改影响已添加的结果）添加到 result 列表中，然后直接返回，结束当前这一轮的递归探索。

4. 处理重复元素与选择元素：
   使用 for 循环遍历 nums 数组，对于每一个元素 nums[i]，需要进行两个重要的条件判断来决定是否使用该元素继续构建排列。

   • 去重判断：
     当 i > 0 且 nums[i] 等于 nums[i - 1]，同时 used[i - 1] 为 false 时，说明当前元素与前一个元素相同，并且前一个相同元素在当前这一轮的排列构建中还未被使用（也就是处于同一 “树枝” 上还没被选过），为了避免产生重复的排列，需要跳过当前这个元素（通过 continue 语句）。例如，对于序列 [1, 1, 2]，如果第一个 1 还没被使用，在遇到第二个 1 时，若不做这个判断就会产生重复的排列情况，所以要跳过这个重复的 1 去尝试其他元素选择。
   • 未使用元素判断：
     如果 used[i] 为 false，表示这个元素还未被使用，可以将其添加到当前的排列 path 中，此时将 used[i] 标记为 true，表示该元素已被选用了。

5. 递归探索与回溯：
   在将元素 nums[i] 添加到 path 中后，接着以这个新的状态递归调用 backTracking 方法，继续去探索后续还可以添加哪些元素来构成完整的全排列。当这一层递归调用结束后（也就是以当前添加的这个元素为基础的所有可能排列情况都探索完了），需要进行回溯操作，先将刚添加到 path 中的元素移除（通过 path.remove(path.size() - 1)），然后把对应的 used[i] 标记回 false，这样就回到了添加这个元素之前的状态，能够去尝试其他的元素选择，继续探索不同的排列组合情况。

6. 最终结果返回：
   在 permuteUnique 主方法中，经过一系列的回溯探索后，result 列表中就收集了所有的不重复全排列情况，最后将其返回。

代码

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used = new boolean[nums.length];
        Arrays.fill(used,false);
        Arrays.sort(nums);
        backTracking(nums,used);
        return result;
    }
    private void backTracking(int[] nums,boolean[] used){
        if(path.size() == nums.length){
            result.add(new ArrayList<>(path));
            return ;
        }
        for(int i = 0;i < nums.length;i++){
            if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
                continue;
            } 
            //如果同一树枝nums[i]没使用过，则开始处理
            if(used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums,used);
                path.remove(path.size() - 1);//回溯
                used[i] = false;
            }
        }
    }
}