Accepted recursive Python solution. 152 ms


  • 0
    X
    class Solution:
        # @param num, a list of integer
        # @return a list of lists of integer
        def subsetsWithDup(self, S):
            result = [[]]
            S.sort()
            def sub(prev, cur, result):
                if cur == []:
                    return
                for i in range(len(cur)):
                    if i == 0 or cur[i] != cur[i-1]:
                        now = prev+[cur[i]]
                        result.append(now)
                        sub(now, cur[i+1:], result)
            sub([], S, result)
            return result
    

    I think this solution is quite straightforward.


  • 0
    M

    Share a similar solution

    def subsetsWithDup(self, S):
        weighted_seq = [(k, len(list(g))) for k, g in itertools.groupby(sorted(S))] 
    
        def bt(i, n, S, cur): 
            if i == n: 
                return [cur] 
            return reduce(operator.add, [bt(i+1, n, S, cur + [S[i][0]]*k) for k in range(S[i][1]+1)])
    
        return bt(0, len(weighted_seq), weighted_seq, [])

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.