LeetCode 78. Subsets

November 10, 2020

The full set of subsets contains all sets with 1 element, with 2 elements, with 3 elements, etc. That means we can build the power set inductively with recursion. We'll use caching to skip repeated work.

I looked this up after I did it and my way is kinda non-standard and less efficient. Caching makes mine asymptotically the same at $O(2^n)$ , but the set cloning stuff I did is much slower in practice than the canonical answer.

from typing import List, Set, FrozenSet, Dict
import unittest

class Test(unittest.TestCase):

    def setUp(self):
        self.s = Solution()

    def test_examples(self):
        self.assertCountEqual(self.s.subsets([1,2,3]), [[3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], []])

class Solution:

    def helper(self, s: Set[int], c: Dict[frozenset, frozenset]) -> Set[FrozenSet[int]]:
        key = frozenset(s)
        if key in c:
            return c[key]
        res = set(frozenset({frozenset()}))
        for x in s:
            res.add(frozenset({x}))
            for ss in self.helper(s-{x}, c):
                res.add(frozenset({x})|ss)
        c[key] = frozenset(res)
        return res

    def subsets(self, nums: List[int]) -> List[List[int]]:
        return [list(ss) for ss in self.helper(set(nums), {})]

if __name__ == "__main__":
    unittest.main()