LeetCode 题解:90. 子集 II,迭代,JavaScript,详细注释
原题链接:https://leetcode-cn.com/problems/subsets-ii/
解题思路:
生成所有子集,实际上要达到的效果是,nums 中的每个元素是否显示在子集中。
假设现在已经生成了 n-1 个元素的子集,当前遍历到第 n 个元素,那么只需要将现有的子集遍历一次,将第 n 个元素加入到现有子集中,形成新的子集即可。
如何去重:
* 关于去重的方法,可以参考题解详细通俗的思路分析,多解法中的迭代法部分,结合我的注释加深理解。
* 如果在不去重的情况下,观察[1, 2, 2]
的所有子集如下:
复制代码
会发现[ 1 2 2 ] 的所有子串 [ ] [ 1 ] [ 2 ] [ 1 2 ] [ 2 ] [ 1 2 ] [ 2 2 ] [ 1 2 2 ]
中,重复的子集是[ 2 ] [ 1 2 ]
,而它们是由[ 1 ] 的所有子集 [ ] [ 1 ]
分别加上2
得到的。
因此我们要做的是,在输出[ 1 2 2 ]
的子集时,排除掉[ 1 ]
的子集。
具体做法就是先保存[ 1 ]
的所有子集长度,然后在第二层遍历中排除掉这部分子集。
同时需要判断nums[i] === nums[i - 1]
,也就是当出现重复元素时,才进行去重,
因为第一次遍历该元素时,已经输出过一次子集。
复制代码
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/65199d6cbc6ff813f08a76fe3】。文章转载请联系作者。
评论