Leetcode 78. Subsets

https://leetcode.com/problems/subsets/

DFS.

Solution:

# T:O(n*2^n) S:O(n)
class Solution:
    # @param S, a list of integer
    # @return a list of lists of integer
    def subsets(self, S):
        return self.subsetsRecu([], sorted(S))
    def subsetsRecu(self, cur, S):
        if not S:
            return [cur]
        return self.subsetsRecu(cur, S[1:]) + self.subsetsRecu(cur + [S[0]], S[1:])

Run Time: 64 ms