題目
給定一個可能具有重復(fù)數(shù)字的列表，返回其所有可能的子集
注意事項
子集中的每個元素都是非降序的
兩個子集間的順序是無關(guān)緊要的
解集中不能包含重復(fù)子集
test case
如果 S = [1,2,2]怔蚌，一個可能的答案為：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
思路
eg:
{1,2',2''}
取{1,2'} {2',2''}
不取 {1,2''} {2'',2‘}
"""
重復(fù)的數(shù)選取第一次出現(xiàn)的,所以只需要在循環(huán)中進(jìn)行處理旁赊，對于不取的情況進(jìn)行跳過。
判斷條件就是
數(shù)組不越界
前后兩個字符相等
當(dāng)前字符不是一次出現(xiàn)即 不等于startIndex
"""
結(jié)果
class Solution:
"""
@param S: A set of numbers.
@return: A list of lists. All valid subsets.
"""
def subsetsWithDup(self, S):
# write your code here
result = []
if (S is None):
return result
def subSetsHelper(nums, startIndex, temp_list, ret):
# 生成新對象
ret.append([] + temp_list)
for i in range(startIndex, len(nums)):
# 先添加,再移除
# 判斷跳過的循環(huán)
if (i != 0 and nums[i] == nums[i - 1] and i != startIndex):
continue
temp_list.append(nums[i])
subSetsHelper(nums, i + 1, temp_list, ret)
temp_list.pop()
S.sort()
subSetsHelper(S, 0, [], result)
return result
