Yuan
0%

78. Subsets

Posted on Edited on

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

Solution1: bottom up dp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def subsets(self, A: List[int]) -> List[List[int]]:
        def f(idx):
            for i in range(len(Z)):
                Z.append(Z[i]+[A[idx]])
            Z.append([A[idx]])
        Z=[]
        S=[]
        A.sort()
        for i in range(len(A)):
            S.append(i)
            f(i)
        Z.append([])
        return Z

Solution2: backtrack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def subsets(self, A: List[int]) -> List[List[int]]:
        def f(start,curr):
            if len(curr)==k:
                Z.append(curr[:])
                return
            for i in range(start,len(A)):
                curr.append(A[i])
                f(i+1,curr)
                curr.pop()
        Z=[]
        for k in range(len(A)+1):
            # length is from 0 to len(A)
            f(0,[])
        return Z