# LeetCode 090Subsets II

## LeetCode 090 Subsets II Problem

``````class Solution(object):
# def subsetsWithDup(self, nums):
#     """
#     :type nums: List[int]
#     :rtype: List[List[int]]
#     """
#     nums.sort()
#     res = []
#     for i in range(1 << len(nums)):
#         res.append(self.get_subsets(nums, i))
#     # remove duplicate
#     final_res = {}
#     for subset in res:
#         hash_key = ''.join([str(t) for t in subset])
#         try:
#             final_res[hash_key]
#         except:
#             final_res[hash_key] = subset
#     return final_res.values()
#
# def get_subsets(self, nums, magic):
#     res = []
#     for i in range(len(nums)):
#         if (1 << i) & magic != 0:
#             res.append(nums[i])
#     return res

def subsetsWithDup(self, nums):
nums.sort()
res = [[]]
begin = 0
for index in range(len(nums)):
if index == 0 or nums[index] != nums[index - 1]:
# generate all
begin = 0
size = len(res)
# use existing subsets to generate new subsets
for j in range(begin, size):
curr = list(res[j])
curr.append(nums[index])
res.append(curr)
# avoid duplicate subsets
begin = size
return res
``````