Profitable Schemes
HardPrompt
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] <= 100
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possible subsets of crimes. We can use a recursive backtracking function to generate every combination. For each combination, we calculate the total profit and the total number of members required. If the combination meets the criteria (profit >= minProfit and members <= n), we count it as a valid scheme.
Algorithm
- Define a recursive function
solve(index, currentProfit, currentMembers). - Base Case: If
indexreaches the end of the crimes list (group.length):- If
currentProfit >= minProfit, it's a valid scheme, so return 1. - Otherwise, return 0.
- If
- Recursive Step: For the crime at
index, there are two choices:- Exclude the crime: Recursively call
solve(index + 1, currentProfit, currentMembers). - Include the crime: If
currentMembers + group[index] <= n, recursively callsolve(index + 1, currentProfit + profit[index], currentMembers + group[index]).
- Exclude the crime: Recursively call
- The total number of schemes is the sum of the results from these two choices.
- The initial call is
solve(0, 0, 0).
Walkthrough
We define a recursive helper function, say solve(index, currentProfit, currentMembers). This function explores all possibilities by either including or excluding each crime one by one.
index: The index of the crime we are currently considering.currentProfit: The accumulated profit from the crimes chosen so far.currentMembers: The total number of members required for the crimes chosen so far.
The function works as follows:
- Base Case: When we have considered all the crimes (
index == group.length), we check if the current scheme is profitable. IfcurrentProfit >= minProfit, we have found one valid scheme. - Recursive Step: For each crime at
index, we have two choices: a. Exclude the crime: We move to the next crime without changingcurrentProfitorcurrentMembers. b. Include the crime: We add the crime's profit and required members to our current totals, but only if the total members do not exceedn.
The total number of profitable schemes is the sum of valid schemes found down all recursive paths. This approach is too slow because it explores 2^C possibilities, where C is the number of crimes.
// This is a conceptual example. A direct implementation would time out.// A correct implementation would return counts from the recursion and handle modulo arithmetic.class Solution { private int count = 0; public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { solve(0, 0, 0, n, minProfit, group, profit); return count; } private void solve(int index, int currentProfit, int currentMembers, int n, int minProfit, int[] group, int[] profit) { if (currentMembers > n) { return; // Prune this path } if (index == group.length) { if (currentProfit >= minProfit) { count++; } return; } // Option 1: Don't commit the current crime solve(index + 1, currentProfit, currentMembers, n, minProfit, group, profit); // Option 2: Commit the current crime solve(index + 1, currentProfit + profit[index], currentMembers + group[index], n, minProfit, group, profit); }}Complexity
Time
O(2^C), where `C` is the number of crimes (`group.length`). For each crime, we have two choices (include or exclude), leading to an exponential number of paths.
Space
O(C), where `C` is the number of crimes. This is for the recursion call stack depth.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to exponential time complexity.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Solutions
Solution
class Solution {public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) { final int mod = (int)1 e9 + 7; int m = group.length; int[][][] f = new int[m + 1][n + 1][minProfit + 1]; for (int j = 0; j <= n; ++j) { f[0][j][0] = 1; } for (int i = 1; i <= m; ++i) { for (int j = 0; j <= n; ++j) { for (int k = 0; k <= minProfit; ++k) { f[i][j][k] = f[i - 1][j][k]; if (j >= group[i - 1]) { f[i][j][k] = (f[i][j][k] + f[i - 1][j - group[i - 1]][Math.max(0, k - profit[i - 1])]) % mod; } } } } return f[m][n][minProfit]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.