#0833Time: 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.
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 modulo109 + 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 <= 100
0 <= minProfit <= 100
1 <= group.length <= 100
1 <= group[i] <= 100
profit.length == group.length
0 <= 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 index reaches the end of the crimes list (group.length):
If currentProfit >= minProfit, it's a valid scheme, so return 1.
Otherwise, return 0.
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 call solve(index + 1, currentProfit + profit[index], currentMembers + group[index]).
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. If currentProfit >= 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 changing currentProfit or currentMembers.
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 exceed n.
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.
1// This is a conceptual example. A direct implementation would time out.2// A correct implementation would return counts from the recursion and handle modulo arithmetic.3class Solution {4 private int count = 0;56 public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {7 solve(0, 0, 0, n, minProfit, group, profit);8 return count;9 }1011 private void solve(int index, int currentProfit, int currentMembers, int n, int minProfit, int[] group, int[] profit) {12 if (currentMembers > n) {13 return; // Prune this path14 }15 if (index == group.length) {16 if (currentProfit >= minProfit) {17 count++;18 }19 return;20 }2122 // Option 1: Don't commit the current crime23 solve(index + 1, currentProfit, currentMembers, n, minProfit, group, profit);2425 // Option 2: Commit the current crime26 solve(index + 1, currentProfit + profit[index], currentMembers + group[index], n, minProfit, group, profit);27 }28}
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.
The brute-force approach recomputes the same subproblems multiple times. For example, the number of ways to achieve a certain profit with a certain number of members from crime i onwards is independent of how we reached that state. We can optimize this by storing the results of subproblems in a memoization table (a multi-dimensional array) and reusing them. This is a classic top-down dynamic programming technique.
Algorithm
Create a 3D array memo[C][N+1][P+1] initialized with a value indicating 'not computed' (e.g., null or -1). C is group.length, N is n, P is minProfit.
Define a recursive function solve(index, members, profit).
Base Case: If index == C, we have considered all crimes. Return 1 if profit >= minProfit, otherwise return 0.
Memoization Check: If memo[index][members][profit] is not null, return the stored value.
Recursive Step:
Calculate ways by skipping the current crime: ways = solve(index + 1, members, profit).
If the current crime can be committed (members + group[index] <= n):
Add the ways by taking the current crime:
1ways = (ways + solve(index + 1, members + group[index], min(minProfit, profit + profit[index]))) % MOD
.
Store the result in memo[index][members][profit] and return it.
The final answer is the result of the initial call solve(0, 0, 0).
Walkthrough
We define a recursive function solve(index, currentMembers, currentProfit) which returns the number of profitable schemes from index to the end, given the currentMembers used and currentProfit earned so far.
The state of our DP is defined by (index, members, profit).
index: The current crime index we are considering.
members: The number of members used so far.
profit: The profit accumulated so far.
To keep the state space manageable, we cap the profit at minProfit. Any profit equal to or greater than minProfit is equivalent for our goal, as we only need to know if the total profit is at leastminProfit.
1class Solution {2 int MOD = 1_000_000_007;3 Integer[][][] memo;4 int N, minP;5 int[] G, P;67 public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {8 this.N = n;9 this.minP = minProfit;10 this.G = group;11 this.P = profit;12 this.memo = new Integer[group.length][n + 1][minProfit + 1];13 return solve(0, 0, 0);14 }1516 private int solve(int index, int currentMembers, int currentProfit) {17 if (index == G.length) {18 return currentProfit >= minP ? 1 : 0;19 }2021 if (memo[index][currentMembers][currentProfit] != null) {22 return memo[index][currentMembers][currentProfit];23 }2425 // Option 1: Don't commit crime 'index'26 int ways = solve(index + 1, currentMembers, currentProfit);2728 // Option 2: Commit crime 'index'29 if (currentMembers + G[index] <= N) {30 ways = (ways + solve(index + 1, currentMembers + G[index], Math.min(minP, currentProfit + P[index]))) % MOD;31 }3233 return memo[index][currentMembers][currentProfit] = ways;34 }35}
Complexity
Time
O(C * N * P). Each state `(index, members, profit)` is computed only once.
Space
O(C * N * P) for the memoization table, plus O(C) for the recursion stack. `C` is `group.length`, `N` is `n`, and `P` is `minProfit`.
Trade-offs
Pros
Significantly more efficient than brute force.
Guaranteed to find the correct solution within the time limits for the given constraints.
Cons
Uses a large amount of memory for the 3D memoization table, which might be a concern for larger constraints.
This approach is an iterative, bottom-up version of the DP solution. It avoids recursion and typically has better performance due to lower overhead. By being careful with the iteration order, we can optimize the space complexity from the 3D table of the memoized solution to a 2D table.
Algorithm
Create a 2D array dp[P+1][N+1] initialized to 0, where P is minProfit and N is n.
dp[p][g] will store the number of schemes with profit exactly p (capped at P) using g members.
Initialize the base case: dp[0][0] = 1, representing the empty scheme with 0 profit and 0 members.
Loop through each crime i:
Let p_i = profit[i] and g_i = group[i].
To avoid using the same crime multiple times in one step, iterate the loops for members and profit backwards.
Loop g from N down to g_i.
Loop p from P down to 0.
A scheme with profit p and g - g_i members can be extended by adding crime i.
After iterating through all crimes, the value dp[P][g] will hold the number of schemes with profit at leastP using g members.
The final answer is the sum of dp[P][g] for all g from 0 to N.
Walkthrough
We define a 2D DP table dp[p][g], where dp[p][g] stores the number of ways to achieve a profit of p using g members. The profit p is capped at minProfit, so the dimensions of this table are (minProfit + 1) x (n + 1). Any scheme with profit greater than or equal to minProfit will be counted in the p = minProfit state.
We iterate through each crime and update the dp table. For each crime, we consider how it can extend existing schemes. To ensure that each crime is used at most once per scheme, we iterate the loops for members and profit backwards. This way, when we compute dp[...][g], we use values from dp[...][g - g_i] that were computed before considering the current crime.
After iterating through all crimes, dp[minProfit][g] will contain the total number of schemes that use g members and achieve a profit of at leastminProfit. The final answer is the sum of these counts over all possible member counts from 0 to n.
1class Solution {2 public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {3 int MOD = 1_000_000_007;4 // dp[p][g] = number of schemes with profit p and g members.5 // Profit is capped at minProfit, so dp[minProfit][g] includes all schemes with profit >= minProfit.6 int[][] dp = new int[minProfit + 1][n + 1];7 dp[0][0] = 1; // Base case: one way to have 0 profit and 0 members (the empty scheme).89 for (int i = 0; i < group.length; i++) {10 int p_i = profit[i];11 int g_i = group[i];1213 // Iterate backwards to use each crime at most once for a given scheme.14 for (int g = n; g >= g_i; g--) {15 for (int p = minProfit; p >= 0; p--) {16 // A scheme with profit p and g - g_i members can be extended by adding the current crime.17 int newProfit = Math.min(minProfit, p + p_i);18 dp[newProfit][g] = (dp[newProfit][g] + dp[p][g - g_i]) % MOD;19 }20 }21 }2223 int totalSchemes = 0;24 for (int g = 0; g <= n; g++) {25 totalSchemes = (totalSchemes + dp[minProfit][g]) % MOD;26 }2728 return totalSchemes;29 }30}
Complexity
Time
O(C * N * P), where `C` is `group.length`, `N` is `n`, and `P` is `minProfit`.
Space
O(N * P), where `N` is `n` and `P` is `minProfit`. This is a space optimization over the 3D DP table.
Trade-offs
Pros
Most efficient in terms of both time and space.
Avoids recursion overhead.
Cons
The logic, especially with state transitions and loop directions, can be less intuitive than the recursive approach.
Solutions
Solution
1class Solution {2public3 int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {4 final int mod = (int)1 e9 + 7;5 int m = group.length;6 int[][][] f = new int[m + 1][n + 1][minProfit + 1];7 for (int j = 0; j <= n; ++j) {8 f[0][j][0] = 1;9 }10 for (int i = 1; i <= m; ++i) {11 for (int j = 0; j <= n; ++j) {12 for (int k = 0; k <= minProfit; ++k) {13 f[i][j][k] = f[i - 1][j][k];14 if (j >= group[i - 1]) {15 f[i][j][k] =16 (f[i][j][k] +17 f[i - 1][j - group[i - 1]][Math.max(0, k - profit[i - 1])]) %18 mod;19 }20 }21 }22 }23 return f[m][n][minProfit];24 }25}
1class Solution {2public:3 int profitableSchemes(int n, int minProfit, vector<int> &group,4 vector<int> &profit) {5 int m = group.size();6 int f[m + 1][n + 1][minProfit + 1];7 memset(f, 0, sizeof(f));8 for (int j = 0; j <= n; ++j) {9 f[0][j][0] = 1;10 }11 const int mod = 1e9 + 7;12 for (int i = 1; i <= m; ++i) {13 for (int j = 0; j <= n; ++j) {14 for (int k = 0; k <= minProfit; ++k) {15 f[i][j][k] = f[i - 1][j][k];16 if (j >= group[i - 1]) {17 f[i][j][k] =18 (f[i][j][k] +19 f[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])]) %20 mod;21 }22 }23 }24 }25 return f[m][n][minProfit];26 }27};
1class Solution:2 def profitableSchemes(self, n: int, minProfit: int, group: List[int], profit: List[int]) -> int: mod = 10 ** 9 + 7 m = len(group) f = [[[0] * (minProfit + 1) for _ in range(n + 1)] for _ in range(m + 1)] for j in range(n + 1): f[0][j][0] = 1 for i, (x, p) in enumerate(zip(group, profit), 1): for j in range(n + 1): for k in range(minProfit + 1): f[i][j][k] = f[i - 1][j][k] if j >= x: f[i][j][k] = (f[i][j][k] + f[i - 1][j - x][max(0, k - p)]) % 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.
