90. 子集 II

原题链接：

90. 子集 II

https://leetcode.cn/problems/subsets-ii/

完成情况：

解题思路：

这段代码是深度优先搜索 (DFS) 算法解决LeetCode问题“子集 II”的一部分。首先，定义了两个变量 result 和 tempList，分别用来存储所有生成的子集和当前正在生成的子集。其中，result 是一个列表，每个元素都是一个子集列表；tempList 是当前操作的子集。然后，在代码中调用了一个函数 dfs_subsetsWithDup 用于递归生成子集。

在主函数中，代码执行了 tempList.add(nums[cur]); 将当前数组元素 nums[cur] 加入到当前子集 tempList 中。接着，通过 dfs_subsetsWithDup(true,cur+1,nums); 递归调用自身，继续往下探索生成子集的可能性。在递归之后，通过 tempList.remove(tempList.size()-1); 移除最后一个元素，以回退到之前状态，准备尝试其他选择。

总的来说，这段代码是在不同情况下不断生成子集的过程，通过DFS算法的深度优先搜索，探索可能的子集组合情况。

参考代码：

_90子集II_递归法求子集

package leetcode板块;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _90子集II_递归法求子集 {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> tempList = new ArrayList<Integer>();

    /**
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums){
        Arrays.sort(nums);
        dfs_subsetsWithDup(false,0,nums);
        return result;
    }

    /**
     *
     * @param choosePre
     * @param cur
     * @param nums
     */
    private void dfs_subsetsWithDup(boolean choosePre, int cur, int[] nums) {
        if (cur == nums.length){
            result.add(new ArrayList<Integer>(tempList));
            return;
        }
        dfs_subsetsWithDup(false,cur + 1,nums);
        if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]){
            return;
        }
        tempList.add(nums[cur]);
        dfs_subsetsWithDup(true,cur+1,nums);
        tempList.remove(tempList.size()-1);
    }
}

_90子集II_迭代法求子集

package leetcode板块;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _90子集II_迭代法求子集 {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    List<Integer> tempList = new ArrayList<Integer>();

    /**
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        //第一步，先将数据元素调整为有序
        Arrays.sort(nums);
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); mask++) {
            tempList.clear();
            boolean flag = true;
            for (int i = 0;i<n;++i){
                if ((mask & (1 << i)) != 0){
                    if (i>0 && (mask >> (i - 1) & 1) == 0 && nums[i] == nums[i-1]){
                        flag = false;
                        break;
                    }
                    tempList.add(nums[i]);
                }
            }
            if (flag){
                result.add(new ArrayList<Integer>(tempList));
            }
        }
        return  result;
    }
}

错误经验吸取