090.子集 II

作者：沉默王二
发布时间：2023-10-15T17:37:55.314+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

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

难度

中等

示例

示例 1：

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

示例 2：

输入：nums=[0]

分析

要枚举一个集合的所有子集，我们可能第一时间想到的是递归与回溯算法，但是这类算法通常会使用大量的栈空间，我们不妨采用另外一种方法——二进制枚举。

二进制枚举的核心思想是利用二进制数的每一位来表示某种状态或选择，从而枚举出所有可能的组合或子集。

以下是对二进制枚举的基本原理进行说明：

①. 基本概念: 在二进制数中，每一位只能是0或1，其中0通常表示“不选择”或“假”，而1表示“选择”或“真”。

②. 应用场景: 当你有一个长度为n的集合或数组，并且你想要枚举其所有可能的子集时，二进制枚举是一种有效的方法。因为一个长度为n的集合总共有2^n个子集（包括空集和整个集合本身）。

看下面的表达式。

的含义是从 个不同元素中取出 个元素的所有不同排列个数，所以上述表达式的意思是 个元素能组合出多少种方式。

③. 枚举过程:

• 对于长度为n的集合，可以使用从0到2^n - 1的整数进行枚举。
• 对于每个整数，将其转换为二进制表示。此时，二进制数中的每一位都对应集合中的一个元素，1表示选择该元素，0表示不选择。
• 例如，对于集合{A, B, C}，整数5的二进制表示是101，表示子集{A, C}。

④. 示例:

如果有一个集合{A, B, C}，则二进制枚举的结果为：

000->{}

010->{B}011->{B,C}100->{A}101->{A,C}110->{A,B}111->{A,B,C}

⑤. 优点:

• 二进制枚举是一种非常直观且易于实现的方法。
• 它可以高效地枚举所有可能的组合，尤其适用于解决与组合、子集相关的问题。

这就是我们进行二进制枚举的根本。那么重复的元素要如何去除呢？

如果有两个重复的元素，则会导致单独选了这两个元素的子集相同。既然相同，直接跳过即可，我们可以将整个nums排序一遍，然后进行二进制枚举，遇到前后一样，并且不是前后两个同时选择的方案，就直接跳过，不加入结果中即可。

例如，考虑数组 [1,2,2]，我们只为第一个2生成子集 [2]，不为第二个2生成相同的子集。

来看完整题解。

classSolution{

List<List>res=newArrayList<>();//t临时存储每个子集Listt=newArrayList<>();publicList<List>subsetsWithDup(int[]nums){//首先对数组进行排序，确保重复的数字相邻Arrays.sort(nums);intsiz=nums.length;//chosen的范围从0到(2^siz)-1,表示所有可能的子集for(intchosen=0;chosen<(1<<siz);chosen++){t.clear();//清空临时列表booleaninsFlag=true;//标志位，表示是否应该插入子集//遍历每一个数字for(inti=0;i<siz;i++){//如果chosen的第i位是1，那么nums[i]应该被添加到子集中if((chosen&(1<<i))!=0){//如果nums[i]和前一个数字相同，且chosen的第i-1位为0（意味着nums[i-1]不在子集中）//那么这是一个重复子集，因此我们设置insFlag为false，并中止循环if(i>0&&(nums[i]==nums[i-1])&&(chosen&(1<<(i-1)))==0){insFlag=false;break;}t.add(nums[i]);//把nums[i]添加到临时子集}}//如果这不是一个重复子集，就添加到res中if(insFlag){res.add(newArrayList<>(t));}}returnres;}}

当 nums = [1,2,2] 时，我们可以使用题解中的方法来模拟整个过程。

首先，对 nums 进行排序（已经是排序的，不用再排序）。

接着，使用二进制枚举来生成所有可能的子集。

• 0 (二进制: 000) ：不选择任何元素 → []
• 1 (二进制: 001) ：选择第一个元素 → [1]
• 2 (二进制: 010) ：选择第二个元素 → [2]
• 3 (二进制: 011) ：选择第一个和第二个元素 → [1,2]
• 4 (二进制: 100) ：选择第三个元素 → [2]，但是这里注意，第三个元素和第二个元素相同，且第二个元素没有被选中，因此我们跳过这个选择，避免产生重复的子集。
• 5 (二进制: 101) ：选择第一个和第三个元素 → [1,2]，但是这是和第四个选择重复的子集，所以也被跳过。
• 6 (二进制: 110) ：选择第二个和第三个元素 → [2,2]
• 7 (二进制: 111) ：选择所有元素 → [1,2,2]

通过上述模拟，我们可以得到所有的子集：

[],[1],[2],[1,2],[2,2],[1,2,2]

关键的步骤是如何避免重复。在这个题解中，通过检查当前元素与前一个元素是否相同，并根据前一个元素是否被选中来决定是否跳过当前选择，从而避免了重复子集的产生。

来看题解的效率。

总结

本题是 078.子集 的加强版，总体上只相差了对重复元素的处理，我们处理的方法也是抓住关键，跳过它。

力扣链接：https://leetcode.cn/problems/subsets-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

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

难度

中等

示例

示例 1：

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

示例 2：

输入：nums=[0]

分析

要枚举一个集合的所有子集，我们可能第一时间想到的是递归与回溯算法，但是这类算法通常会使用大量的栈空间，我们不妨采用另外一种方法——二进制枚举。

二进制枚举的核心思想是利用二进制数的每一位来表示某种状态或选择，从而枚举出所有可能的组合或子集。

以下是对二进制枚举的基本原理进行说明：

①. 基本概念: 在二进制数中，每一位只能是0或1，其中0通常表示“不选择”或“假”，而1表示“选择”或“真”。

②. 应用场景: 当你有一个长度为n的集合或数组，并且你想要枚举其所有可能的子集时，二进制枚举是一种有效的方法。因为一个长度为n的集合总共有2^n个子集（包括空集和整个集合本身）。

看下面的表达式。

的含义是从 个不同元素中取出 个元素的所有不同排列个数，所以上述表达式的意思是 个元素能组合出多少种方式。

③. 枚举过程:

• 对于长度为n的集合，可以使用从0到2^n - 1的整数进行枚举。
• 对于每个整数，将其转换为二进制表示。此时，二进制数中的每一位都对应集合中的一个元素，1表示选择该元素，0表示不选择。
• 例如，对于集合{A, B, C}，整数5的二进制表示是101，表示子集{A, C}。

④. 示例:

如果有一个集合{A, B, C}，则二进制枚举的结果为：

000->{}

010->{B}011->{B,C}100->{A}101->{A,C}110->{A,B}111->{A,B,C}

⑤. 优点:

• 二进制枚举是一种非常直观且易于实现的方法。
• 它可以高效地枚举所有可能的组合，尤其适用于解决与组合、子集相关的问题。

这就是我们进行二进制枚举的根本。那么重复的元素要如何去除呢？

如果有两个重复的元素，则会导致单独选了这两个元素的子集相同。既然相同，直接跳过即可，我们可以将整个nums排序一遍，然后进行二进制枚举，遇到前后一样，并且不是前后两个同时选择的方案，就直接跳过，不加入结果中即可。

例如，考虑数组 [1,2,2]，我们只为第一个2生成子集 [2]，不为第二个2生成相同的子集。

来看完整题解。

classSolution{

List<List>res=newArrayList<>();//t临时存储每个子集Listt=newArrayList<>();publicList<List>subsetsWithDup(int[]nums){//首先对数组进行排序，确保重复的数字相邻Arrays.sort(nums);intsiz=nums.length;//chosen的范围从0到(2^siz)-1,表示所有可能的子集for(intchosen=0;chosen<(1<<siz);chosen++){t.clear();//清空临时列表booleaninsFlag=true;//标志位，表示是否应该插入子集//遍历每一个数字for(inti=0;i<siz;i++){//如果chosen的第i位是1，那么nums[i]应该被添加到子集中if((chosen&(1<<i))!=0){//如果nums[i]和前一个数字相同，且chosen的第i-1位为0（意味着nums[i-1]不在子集中）//那么这是一个重复子集，因此我们设置insFlag为false，并中止循环if(i>0&&(nums[i]==nums[i-1])&&(chosen&(1<<(i-1)))==0){insFlag=false;break;}t.add(nums[i]);//把nums[i]添加到临时子集}}//如果这不是一个重复子集，就添加到res中if(insFlag){res.add(newArrayList<>(t));}}returnres;}}

当 nums = [1,2,2] 时，我们可以使用题解中的方法来模拟整个过程。

首先，对 nums 进行排序（已经是排序的，不用再排序）。

接着，使用二进制枚举来生成所有可能的子集。

• 0 (二进制: 000) ：不选择任何元素 → []
• 1 (二进制: 001) ：选择第一个元素 → [1]
• 2 (二进制: 010) ：选择第二个元素 → [2]
• 3 (二进制: 011) ：选择第一个和第二个元素 → [1,2]
• 4 (二进制: 100) ：选择第三个元素 → [2]，但是这里注意，第三个元素和第二个元素相同，且第二个元素没有被选中，因此我们跳过这个选择，避免产生重复的子集。
• 5 (二进制: 101) ：选择第一个和第三个元素 → [1,2]，但是这是和第四个选择重复的子集，所以也被跳过。
• 6 (二进制: 110) ：选择第二个和第三个元素 → [2,2]
• 7 (二进制: 111) ：选择所有元素 → [1,2,2]

通过上述模拟，我们可以得到所有的子集：

[],[1],[2],[1,2],[2,2],[1,2,2]

关键的步骤是如何避免重复。在这个题解中，通过检查当前元素与前一个元素是否相同，并根据前一个元素是否被选中来决定是否跳过当前选择，从而避免了重复子集的产生。

来看题解的效率。

总结

本题是 078.子集 的加强版，总体上只相差了对重复元素的处理，我们处理的方法也是抓住关键，跳过它。

力扣链接：https://leetcode.cn/problems/subsets-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

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

难度

中等

示例

示例 1：

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

示例 2：

输入：nums=[0]

分析

要枚举一个集合的所有子集，我们可能第一时间想到的是递归与回溯算法，但是这类算法通常会使用大量的栈空间，我们不妨采用另外一种方法——二进制枚举。

二进制枚举的核心思想是利用二进制数的每一位来表示某种状态或选择，从而枚举出所有可能的组合或子集。

以下是对二进制枚举的基本原理进行说明：

①. 基本概念: 在二进制数中，每一位只能是0或1，其中0通常表示“不选择”或“假”，而1表示“选择”或“真”。

②. 应用场景: 当你有一个长度为n的集合或数组，并且你想要枚举其所有可能的子集时，二进制枚举是一种有效的方法。因为一个长度为n的集合总共有2^n个子集（包括空集和整个集合本身）。

看下面的表达式。

的含义是从 个不同元素中取出 个元素的所有不同排列个数，所以上述表达式的意思是 个元素能组合出多少种方式。

③. 枚举过程:

• 对于长度为n的集合，可以使用从0到2^n - 1的整数进行枚举。
• 对于每个整数，将其转换为二进制表示。此时，二进制数中的每一位都对应集合中的一个元素，1表示选择该元素，0表示不选择。
• 例如，对于集合{A, B, C}，整数5的二进制表示是101，表示子集{A, C}。

④. 示例:

如果有一个集合{A, B, C}，则二进制枚举的结果为：

000->{}

010->{B}011->{B,C}100->{A}101->{A,C}110->{A,B}111->{A,B,C}

⑤. 优点:

• 二进制枚举是一种非常直观且易于实现的方法。
• 它可以高效地枚举所有可能的组合，尤其适用于解决与组合、子集相关的问题。

这就是我们进行二进制枚举的根本。那么重复的元素要如何去除呢？

如果有两个重复的元素，则会导致单独选了这两个元素的子集相同。既然相同，直接跳过即可，我们可以将整个nums排序一遍，然后进行二进制枚举，遇到前后一样，并且不是前后两个同时选择的方案，就直接跳过，不加入结果中即可。

例如，考虑数组 [1,2,2]，我们只为第一个2生成子集 [2]，不为第二个2生成相同的子集。

来看完整题解。

classSolution{

List<List>res=newArrayList<>();//t临时存储每个子集Listt=newArrayList<>();publicList<List>subsetsWithDup(int[]nums){//首先对数组进行排序，确保重复的数字相邻Arrays.sort(nums);intsiz=nums.length;//chosen的范围从0到(2^siz)-1,表示所有可能的子集for(intchosen=0;chosen<(1<<siz);chosen++){t.clear();//清空临时列表booleaninsFlag=true;//标志位，表示是否应该插入子集//遍历每一个数字for(inti=0;i<siz;i++){//如果chosen的第i位是1，那么nums[i]应该被添加到子集中if((chosen&(1<<i))!=0){//如果nums[i]和前一个数字相同，且chosen的第i-1位为0（意味着nums[i-1]不在子集中）//那么这是一个重复子集，因此我们设置insFlag为false，并中止循环if(i>0&&(nums[i]==nums[i-1])&&(chosen&(1<<(i-1)))==0){insFlag=false;break;}t.add(nums[i]);//把nums[i]添加到临时子集}}//如果这不是一个重复子集，就添加到res中if(insFlag){res.add(newArrayList<>(t));}}returnres;}}

当 nums = [1,2,2] 时，我们可以使用题解中的方法来模拟整个过程。

首先，对 nums 进行排序（已经是排序的，不用再排序）。

接着，使用二进制枚举来生成所有可能的子集。

• 0 (二进制: 000) ：不选择任何元素 → []
• 1 (二进制: 001) ：选择第一个元素 → [1]
• 2 (二进制: 010) ：选择第二个元素 → [2]
• 3 (二进制: 011) ：选择第一个和第二个元素 → [1,2]
• 4 (二进制: 100) ：选择第三个元素 → [2]，但是这里注意，第三个元素和第二个元素相同，且第二个元素没有被选中，因此我们跳过这个选择，避免产生重复的子集。
• 5 (二进制: 101) ：选择第一个和第三个元素 → [1,2]，但是这是和第四个选择重复的子集，所以也被跳过。
• 6 (二进制: 110) ：选择第二个和第三个元素 → [2,2]
• 7 (二进制: 111) ：选择所有元素 → [1,2,2]

通过上述模拟，我们可以得到所有的子集：

[],[1],[2],[1,2],[2,2],[1,2,2]

关键的步骤是如何避免重复。在这个题解中，通过检查当前元素与前一个元素是否相同，并根据前一个元素是否被选中来决定是否跳过当前选择，从而避免了重复子集的产生。

来看题解的效率。

总结

本题是 078.子集 的加强版，总体上只相差了对重复元素的处理，我们处理的方法也是抓住关键，跳过它。

力扣链接：https://leetcode.cn/problems/subsets-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412