给定一组
不含重复元素
的整数数组
nums
,返回该数组所有可能的子集(幂集)。
说明:
解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
观察全排列/组合/子集问题,它们比较相似,且可以使用一些通用策略解决。
首先,它们的解空间非常大:
-
全排列
:N!。 -
组合
:N!。 -
子集:2^N,每个元素都可能存在或不存在。
-
在它们的指数级解法中,要确保生成的结果 完整 且 无冗余,有三种常用的方法:
递归
回溯
基于二进制位掩码和对应位掩码之间的映射字典生成排列/组合/子集
相比前两种方法,第三种方法将每种情况都简化为二进制数,易于实现和验证。
此外,第三种方法具有最优的时间复杂度,可以生成按照字典顺序的输出结果。
解法一:递归!利用数学归纳法的思
版权声明:本文为blue_coffeei原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。