Problem statement

https://leetcode.com/problems/profitable-schemes/

Solution

Question we need to answer here is the following: given numbers $[p_0, \dots, p_{n-1}]$ and $[g_0, \dots g_{n-1}]$ how many subsets there are, such that: \(p_{i_1} + \dots + p_{i_k} \geqslant P, \ \ \ g_{i_1} + \dots g_{i_k} \leqslant G.\) The problem if we write is like this, is that first sum is not bounded from above, so let us solve two different problems:

  1. $p_{i_1} + \dots + p_{i_k} \leqslant P - 1, \ \ \ g_{i_1} + \dots g_{i_k} \leqslant G$, for which we will use dfs1(i, j, l) function. Here i is current profit we have, j is how many people we used and l is number of crime we are working with. Function dfs1(P - 1, G, n - 1) will answer a question: how many solutions we have.
  2. $g_{i_1} + \dots g_{i_k} \leqslant G$, for which we will use dfs2(j, l) function. Similar to previous function, here we have only two states: j is how many people we used and l is number of crime we are working with.

Complexity

Time complexity is O(nPG), space as well.

Code 1

class Solution:
    def profitableSchemes(self, G, P, group, profit):
        n, MOD = len(group), 10**9 + 7
        @lru_cache(None)
        def dfs1(i, j, l):
            if l == -1: return 1
            ans = dfs1(i, j, l - 1)
            if i - profit[l] >= 0 and j - group[l] >= 0:
                ans += dfs1(i - profit[l], j - group[l], l - 1)  
            return ans % MOD
        
        @lru_cache(None)
        def dfs2(j, l):
            if l == -1: return 1 
            ans = dfs2(j, l - 1)
            if j - group[l] >= 0:
                ans += dfs2(j - group[l], l - 1)
            return ans % MOD

        return (dfs2(G, n - 1) - dfs1(P - 1, G, n - 1)) % MOD

Code 2

Actually, it can be written in shorter way, with the same complexity.

class Solution:
    def profitableSchemes(self, G, P, group, profit):
        n, MOD = len(group), 10**9 + 7
        @lru_cache(None)
        def dfs(i, j, l):
            if l == -1: return i == 0
            ans = dfs(i, j, l - 1)
            if j - group[l] >= 0:
                ans += dfs(max(0, i - profit[l]), j - group[l], l - 1)  
            return ans % MOD

        return dfs(P, G, n - 1)