Efficient solution for the coin change problem in python

coinchange.py

"""Find all number of combinations that formed a sum (N) amount with given denominations (A)"""
"""The combinations can be indexed with I and for the same I the same permutation is returned every time"""

from typing import List, Dict, Set, Tuple
from tqdm import tqdm
import sys

MAX_CACHE_SIZE = 1000000
USE_PRUNE = True

class Solver:

    def __init__(self, I: int, A: List[int]):
        self.I = I
        self.A = sorted(A, reverse=True)
        self.reset()

    def use_cache(self, solver):
        self._cache = solver._cache
        self._cached = solver._cached

    def reset(self):
        self._solutions = []
        self._counter = 0
        self._cache = dict()
        self._cached = set()

    def fetch(self, remaining: int, first_value: int):
        if (remaining, first_value) in self._cached:
            return self._cache[(remaining, first_value)]
        return None

    def save(self, remaining: int, first_value: int, n_possibilities: int):
        if len(self._cache) >= MAX_CACHE_SIZE:
            return
        self._cache[(remaining, first_value)] = n_possibilities
        self._cached.add((remaining, first_value))

    def solve(self, remaining: int, current_path: List[int]) -> List[int]:
        if self._counter == self.I: return
        counter_in = self._counter
        for v in self.A:
            if self._counter == self.I: return
            # only monotonic is allowed
            if len(current_path) > 0 and v > current_path[-1]: continue
            if v > remaining: continue
            # hit
            elif v == remaining:
                self._counter += 1
                self._solutions.append(current_path + [v])
            # dfs
            else:
                cv = remaining - v
                n_perm = self.fetch(cv, v)
                if USE_PRUNE and n_perm is not None and self._counter + n_perm < self.I:
                    self._counter += n_perm
                    continue
                self.solve(remaining - v, current_path + [v])
                
        
        counter_diff = self._counter - counter_in
        if counter_diff > 0:
            if len(current_path) > 0:
                self.save(remaining, current_path[-1], counter_diff)

def solve(i: int, N: int, values: List[int], solver: Solver):
    s = Solver(i, values)
    if solver is not None:
        s.use_cache(solver)
    s.solve(N, [])
    return s._solutions[-1], s

if __name__ == '__main__':
    values = [68, 290, 390, 438, 643, 712, 718, 768, 898, 956]
    N = 1000000

    # set recursion limit for worst case scenario
    reclim = int(N / min(values))
    sys.setrecursionlimit(reclim)
    print("RECURSION LIMIT", reclim)
    
    s = None
    for i in tqdm(range(1, 130158+1), total=130158):
        combination_i, s = solve(i, N, values, s)