There is a group of n members, and a list of various crimes they could commit. The ith crime generates a profit[i] and requires group[i] members to participate in it. If a member participates in one crime, that member can't participate in another crime.
Let's call a profitable scheme any subset of these crimes that generates at least minProfit profit, and the total number of members participating in that subset of crimes is at most n.
Return the number of schemes that can be chosen. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 5, minProfit = 3, group = [2,2], profit = [2,3] Output: 2 Explanation: 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.
Example 2:
Input: n = 10, minProfit = 5, group = [2,3,5], profit = [6,7,8] Output: 7 Explanation: 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).
Constraints:
1 <= n <= 1000 <= minProfit <= 1001 <= group.length <= 1001 <= group[i] <= 100profit.length == group.length0 <= profit[i] <= 100Problem Overview: You are given a set of crimes where each crime requires a certain number of members and generates some profit. With at most n members available, count how many subsets of crimes generate at least minProfit. Each crime can be chosen once, and the answer must be returned modulo 1e9 + 7.
Approach 1: Brute Force Subset Enumeration (Time: O(2^m), Space: O(m))
The most direct idea is to generate every subset of crimes and check whether it satisfies both constraints: total members used ≤ n and total profit ≥ minProfit. You iterate through all 2^m subsets, accumulate the group size and profit for each, and count valid schemes. This approach demonstrates the core combinatorial nature of the problem but quickly becomes infeasible when m grows (up to 100). The exponential complexity makes it unsuitable for real inputs.
Approach 2: 3D Dynamic Programming (Time: O(m * n * minProfit), Space: O(m * n * minProfit))
The key observation is that this is a constrained subset counting problem. Define a DP state dp[i][g][p] representing the number of ways to consider the first i crimes, using g members, and achieving profit p. For each crime, you either skip it or include it. When including it, update the member count and clamp profit to minProfit because anything beyond the target is equivalent for counting purposes. This transforms the exponential search into a structured dynamic programming solution over crime index, group size, and profit states. The approach is clear and systematic but consumes significant memory.
Approach 3: Space-Optimized DP (Time: O(m * n * minProfit), Space: O(n * minProfit))
The crime index dimension is unnecessary because each transition depends only on the previous state. Collapse the DP into a 2D table dp[g][p], where g is the number of members used and p is the profit achieved. Iterate through each crime and update the table in reverse order of members to avoid overwriting states needed in the same iteration. Profit is updated as newProfit = min(minProfit, p + profit[i]) so all profits beyond the threshold accumulate in the same bucket. This reduces space significantly while keeping the same time complexity. The technique is common in knapsack-style problems involving arrays and dynamic programming.
Recommended for interviews: The space-optimized DP is the expected solution. Interviewers want to see the recognition that this is a variation of the 0/1 knapsack counting problem with two constraints (members and profit). Mentioning the brute force approach shows you understand the combinatorial search space, but implementing the optimized DP demonstrates strong dynamic programming skills and awareness of state compression techniques.
This approach leverages dynamic programming to efficiently determine the number of profitable schemes. We use a 3D DP array where dp[i][j][k] represents the number of ways to select from the first i crimes such that exactly j members are used and at least k profit is generated. We iterate over each crime and update our DP table based on whether we include the crime or not in our solution set.
The function `profitableSchemes` initializes a 3D dynamic programming table to track the number of schemes. It iterates over each crime, updating the possible member and profit counts. Each crime decision updates the DP table based on whether the crime is included in the solution set. The final result is obtained by summing up all combinations that meet or exceed the minimum profit using at most the total number of members.
Time Complexity: O(L * N * P), where L is the number of crimes, N is the max number of members, and P is minProfit. Space Complexity: O(L * N * P) due to the DP table.
We design a function dfs(i, j, k), which means that we start from the i-th job, and have chosen j employees, and the current profit is k, then the number of schemes in this case is dfs(0, 0, 0).
The execution process of function dfs(i, j, k) is as follows:
i = n, it means that all the jobs have been considered. If k geq minProfit, the number of schemes is 1, otherwise the number of schemes is 0;i < n, we can choose not to choose the i-th job, then the number of schemes is dfs(i + 1, j, k); if j + group[i] leq n, we can also choose the i-th job, then the number of schemes is dfs(i + 1, j + group[i], min(k + profit[i], minProfit)). Here we limit the profit upper limit to minProfit, because the profit exceeding minProfit has no effect on our answer.Finally, return dfs(0, 0, 0).
In order to avoid repeated calculation, we can use the method of memoization. We use a three-dimensional array f to record all the results of dfs(i, j, k). When we calculate the value of dfs(i, j, k), we store it in f[i][j][k]. When we call dfs(i, j, k), if f[i][j][k] has been calculated, we return f[i][j][k] directly.
The time complexity is O(m times n times minProfit), and th e space complexity is O(m times n times minProfit). Here m and n are the number of jobs and employees, and minProfit is the minimum profit.
We define f[i][j][k] to be the number of schemes to make a profit of at least k with i jobs and j workers. Initially, we have f[0][j][0] = 1, which means that there is only one scheme to make a profit of 0 without any jobs.
For the i-th job, we can choose to work or not to work. If we do not work, then f[i][j][k] = f[i - 1][j][k]; if we work, then f[i][j][k] = f[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]. We need to enumerate j and k, and add up all the schemes.
The final answer is f[m][n][minProfit].
The time complexity is O(m times n times minProfit), and the space complexity is O(m times n times minProfit). Here m and n are the numbers of jobs and workers, and minProfit is the minimum profit to make.
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(L * N * P), where L is the number of crimes, N is the max number of members, and P is minProfit. Space Complexity: O(L * N * P) due to the DP table. |
| recursion with memoization | — |
| Dynamic Programming | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subset Enumeration | O(2^m) | O(m) | Conceptual baseline to understand the subset search space |
| 3D Dynamic Programming | O(m * n * minProfit) | O(m * n * minProfit) | Clear DP formulation when learning the state transitions |
| Space-Optimized 2D DP | O(m * n * minProfit) | O(n * minProfit) | Optimal solution for interviews and production code |
Profitable Schemes - Leetcode 879 - Python • NeetCodeIO • 9,602 views views
Watch 9 more video solutions →Practice Profitable Schemes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor