lintcode練習-18.サブセットII
940 ワード
18.サブセットII
重複する数値を持つ可能性のあるリストを指定し、可能なすべてのサブセットを返します.
サンプル
S=
に挑戦
再帰と非再帰を同時に解決できますか?
注意事項サブセットの各要素は、非降順の である.の2つのサブセット間の順序は、重要でない である.デセットは重複サブセット を含むことができない.
重複する数値を持つ可能性のあるリストを指定し、可能なすべてのサブセットを返します.
サンプル
S=
[1,2,2]の場合、可能な答えは次のとおりです.[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]に挑戦
再帰と非再帰を同時に解決できますか?
注意事項
class Solution:
"""
@param nums: A set of numbers.
@return: A list of lists. All valid subsets.
"""
def subsetsWithDup(self, nums):
# write your code here
self.results = []
self.search(sorted(nums), [], 0)
return self.results
def search(self, nums, S, index):
self.results.append(S[:])
for i in range(index, len(nums)):
if i!=index and nums[i] == nums[i-1]:
continue
S.append(nums[i])
self.search(nums, S, i+1)
S.pop()