<p>There is a group of <code>n</code> members, and a list of various crimes they could commit. The <code>i<sup>th</sup></code> crime generates a <code>profit[i]</code> and requires <code>group[i]</code> members to participate in it. If a member participates in one crime, that member can&#39;t participate in another crime.</p>

<p>Let&#39;s call a <strong>profitable scheme</strong> any subset of these crimes that generates at least <code>minProfit</code> profit, and the total number of members participating in that subset of crimes is at most <code>n</code>.</p>

<p>Return the number of schemes that can be chosen. Since the answer may be very large, <strong>return it modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 5, minProfit = 3, group = [2,2], profit = [2,3]
<strong>Output:</strong> 2
<strong>Explanation:</strong> To make a profit of at least 3, the group could either commit crimes 0 and 1, or just crime 1.
In total, there are 2 schemes.</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8]
<strong>Output:</strong> 7
<strong>Explanation:</strong> To make a profit of at least 5, the group could commit any crimes, as long as they commit one.
There are 7 possible schemes: (0), (1), (2), (0,1), (0,2), (1,2), and (0,1,2).</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 100</code></li>
	<li><code>0 &lt;= minProfit &lt;= 100</code></li>
	<li><code>1 &lt;= group.length &lt;= 100</code></li>
	<li><code>1 &lt;= group[i] &lt;= 100</code></li>
	<li><code>profit.length == group.length</code></li>
	<li><code>0 &lt;= profit[i] &lt;= 100</code></li>
</ul>

class Solution:
    def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int:
        # dp[j][k] means number of ways for j people with min k profit

        # backtrack with memorization
        MOD = 10 ** 9 + 7
        memo: Dict[Tuple[int, int, int], int] = {}  # Memoization dictionary

        def _profitableSchemes(n: int, mp: int, index: int) -> int:
            # If the state (n, mp, index) has been computed before, return its value.
            if (n, mp, index) in memo:
                return memo[(n, mp, index)]

            # If minimum profit requirement is met, count this scheme as 1 way.
            if mp <= 0:
                mp = 0  # Ensuring mp doesn't go below zero

            # If we have considered all crimes, only one scheme is possible when mp <= 0.
            if index == len(group):
                return 1 if mp == 0 else 0

            # Number of ways without committing the current crime
            total_ways = _profitableSchemes(n, mp, index + 1) 

            # Number of ways including the current crime (if feasible)
            if group[index] <= n:
                total_ways += _profitableSchemes(n - group[index], mp - profit[index], index + 1)

            # Store the computed value in the memo dictionary
            memo[(n, mp, index)] = total_ways % MOD
            return memo[(n, mp, index)]

        # Start backtracking with initial parameters
        return _profitableSchemes(n, minProfit, 0)

        # self.ans = 0

        # def _profitableSchemes(n, mp, index):
        #     if mp <= 0:
        #         self.ans += 1

        #     for i in range(index, len(group)):
        #         if group[i] <= n:
        #             _profitableSchemes(n - group[i], mp - profit[i], i + 1)
        #     return 
        
        # _profitableSchemes(n, minProfit, 0)
        # return self.ans % (10 ** 9 + 7)

        
292972