Problem statement

https://binarysearch.com/problems/Factorial-Sum/

Solution

There will be only 12 small enough factorials and we can check all 2^12 sums.

Complexity

It is O(2^k), where k = 12 is total number of different factorials.

Code

class Solution:
    def solve(self, n):
        arr = [factorial(x) for x in range(1, 13)]
        sums = set([0])
        for x in arr:
            sums = sums | set([x + i for i in sums])

        return n in sums