subset sum with memoization

subsum.py

from random import randrange
from functools import lru_cache
from bisect import bisect_right

arr = [randrange(100000) for _ in range(2000)]
arr.sort()

import sys
sys.setrecursionlimit(20000)


@lru_cache()
def subsum(n, i=len(arr)-1) -> bool:
    assert n < 100000
    if i < 0 or n < 0:
        return False
    if n == 0:
        return True
    i = bisect_right(arr, n, hi=i)
    return subsum(n - arr[i], i - 1) or subsum(n, i - 1)