LintCode 18. 子集 II
题目描述
给定一个可能具有重复数字的列表，返回其所有可能的子集。
测试样例
输入：[0]
输出：
[
[],
[0]
]
输入：[1,2,2]
输出：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
解题思路
1、DFS
主要两点：
i). 在每次的深搜过程中，首先将当前子集加入到最终结果；
ii). 深搜时若当前取出的数字不是当前数组的第一个数，且其与前一个数字相同，那么直接略过，因为它与后面数字的组合已被前一个数字的情况覆盖
2、非递归解法（BFS）
类似于BFS，使用栈，栈中的元素是tuple，每个tuple代表当前子集以及对应的起始index。可以将栈每次弹出的元素看作是当前的根节点，然后从其index+1的位置开始入栈，index+1可看作是下一level的节点的起始index。
同样地，这里也需要去重，方法是若下一level的节点不是该level的第一个节点，且与前一个节点相同，那么则略过，因为其与再下一level的节点的组合已被同level的前一个节点的情况覆盖。
代码
1、DFS
class Solution:
"""
@param nums: A set of numbers.
@return: A list of lists. All valid subsets.
"""
def subsetsWithDup(self, nums):
if not nums:
return [[]]
if len(nums) == 1:
return [[], nums]
nums.sort()
result = []
self.dfs(nums, [], result)
return result
def dfs(self, nums, subset, result):
# 每次先将当前子集加入结果中
result.append(subset)
for i, n in enumerate(nums):
# 若当前取出来的数字不是当前数组的第一个数
# 并且其和前一个数字相同，
# 那么从它开始的各种组合已经被其前一个数字的各种组合覆盖
if i and n == nums[i - 1]:
continue
# 使用subset + [n]的方式可以免去append()和pop()操作
self.dfs(nums[i + 1:], subset + [n], result)
class Solution:
"""
@param nums: A set of numbers.
@return: A list of lists. All valid subsets.
"""
def subsetsWithDup(self, nums):
if not nums:
return [[]]
if len(nums) == 1:
return [[], nums]
nums.sort()
result = []
# 将整个序列看作一棵树进行BFS
# 栈中每个元素都是tuple
# 类似于宽搜，代表当前根节点及其位置
stack = [([], -1)]
while stack:
subset, idx = stack.pop()
result.append(subset)
# start是下一level的第一个节点的index
start = idx + 1
for i in range(start, len(nums)):
# 这个循环内部类似于BFS，
# 循环中每次取出来的数字都在同一level，
# 因此若其与前一个相同，
# 则其与下一层节点的组合也相同，因此略过
if i > start and nums[i] == nums[i - 1]:
continue
stack.append((subset + [nums[i]], i))
return result
