lintcode練習-18.サブセットII

18.サブセットII
重複する数値を持つ可能性のあるリストを指定し、可能なすべてのサブセットを返します.
サンプル
S=[1,2,2]の場合、可能な答えは次のとおりです.

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

に挑戦
再帰と非再帰を同時に解決できますか?
注意事項

サブセットの各要素は、非降順の

である.

の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()