subset.py

subset.py

class Solution:
    def subsets(self, S):
        self.ht = {}
        ret = [[]]
        s_sorted = sorted(S)
        for set_length in range(1, len(S)+1):
            ret += self.subset(s_sorted, 0, set_length)
        return ret

    def subset(self, S, index, l):
        if l <= 0:
            ret = self.ht[(index,l)] = [[]]
            return ret
        if len(S)-index == l:
            ret = self.ht[(index,l)] = [S[index:]]
            return ret

        ret = []
        for i in range(index, len(S)-l+1):
            if i != index and S[i] == S[i-1]:
                continue
            rest = self.subset(S, i+1, l-1)
            for x in rest:
                ret.append([S[i]]+x)
        self.ht[(index, l)] = ret
        return ret