LeetCode 879 - Profitable Schemes

This problem asks us to count how many subsets of crimes satisfy two constraints simultaneously: 1. The total number of members used is at most n 2.

leetcodehardarraydynamic-programming

LeetCode Problem 879

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

This problem asks us to count how many subsets of crimes satisfy two constraints simultaneously:

  1. The total number of members used is at most n
  2. The total profit earned is at least minProfit

Each crime has two properties:

  • group[i], the number of members required
  • profit[i], the profit generated

A member cannot participate in multiple crimes, which means the total members used across selected crimes cannot exceed n.

We are not trying to maximize profit or minimize members. Instead, we must count all valid subsets of crimes.

The important detail is that this is a subset selection problem. Every crime can either:

  • be included in the scheme
  • or be excluded

That immediately suggests a combinatorial search space of size 2^m, where m = len(group).

The output is the number of valid subsets whose:

  • total members used <= n
  • total profit >= minProfit

Because the answer can become extremely large, we return the result modulo 10^9 + 7.

The constraints are critical:

  • n <= 100
  • minProfit <= 100
  • number of crimes <= 100

These values are too large for brute force subset enumeration, since 2^100 is astronomically large. However, they are small enough for dynamic programming indexed by:

  • number of members used
  • accumulated profit

An important observation is that profit values larger than minProfit do not need to be distinguished. Once we reach minProfit, additional profit does not change validity. This allows us to cap the profit dimension at minProfit.

Some important edge cases include:

  • minProfit = 0, where even the empty subset is valid
  • crimes with profit[i] = 0
  • crimes requiring more members than currently available
  • combinations where many different subsets produce the same profit and member counts
  • ensuring we do not double count subsets during DP transitions

Approaches

Brute Force

The brute force solution tries every possible subset of crimes.

For each subset:

  1. Compute total members used
  2. Compute total profit earned
  3. Check whether:
  • members used <= n
  • profit >= minProfit

If both conditions hold, increment the answer.

This works because every possible scheme is explicitly examined exactly once.

However, if there are m crimes, there are 2^m subsets. Since m can be as large as 100, this approach is completely infeasible.

Key Insight

The key observation is that this is a constrained subset counting problem, which is a classic dynamic programming pattern similar to 0/1 knapsack.

Each crime contributes:

  • some member cost
  • some profit gain

At every step, we decide whether to include or exclude the crime.

The DP state must track:

  • how many members are currently used
  • how much profit has been accumulated

Since any profit larger than minProfit is equivalent for validity purposes, we clamp profits using:

newProfit = min(minProfit, currentProfit + crimeProfit)

This dramatically reduces the DP state space.

We use dynamic programming where:

dp[members][profit]

stores the number of ways to achieve:

  • exactly members members used
  • at least profit profit accumulated, capped at minProfit

This transforms an exponential subset enumeration problem into a polynomial-time DP solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^m * m) O(1) Enumerates every subset of crimes
Optimal O(m * n * minProfit) O(n * minProfit) Dynamic programming with profit capping

Here, m is the number of crimes.

Algorithm Walkthrough

Step 1: Define the DP State

We create a 2D DP table:

dp[members][profit]

where:

  • members ranges from 0 to n
  • profit ranges from 0 to minProfit

Each cell stores the number of schemes that achieve that state.

The profit dimension is capped at minProfit because profits larger than that are equivalent.

Step 2: Initialize the Base Case

Initially, before selecting any crimes:

  • we use 0 members
  • we earn 0 profit

So:

dp[0][0] = 1

This represents the empty subset.

Step 3: Process Crimes One by One

For every crime:

  • required members = g
  • generated profit = p

we decide whether to include it in existing schemes.

This is a classic 0/1 knapsack transition.

Step 4: Iterate Backwards

We iterate member counts backwards:

for members from n down to g

Backward iteration prevents reusing the same crime multiple times in the same iteration.

Similarly, we iterate profits backwards.

Step 5: Transition States

Suppose we already have:

dp[oldMembers][oldProfit]

If we include the current crime:

newMembers = oldMembers + g
newProfit = min(minProfit, oldProfit + p)

Then:

dp[newMembers][newProfit] += dp[oldMembers][oldProfit]

We take modulo 10^9 + 7.

Step 6: Compute Final Answer

Any state with:

profit == minProfit

represents a valid profitable scheme.

So the answer is:

sum(dp[members][minProfit] for members in range(n + 1))

Why it works

The DP maintains the invariant that after processing the first i crimes:

dp[members][profit]

equals the number of subsets among those crimes that use exactly members members and achieve the capped profit level profit.

Each crime is processed exactly once, and backward iteration guarantees that a crime cannot be reused multiple times. Since every subset corresponds to a unique sequence of include/exclude decisions, every valid scheme is counted exactly once.

Python Solution

from typing import List

class Solution:
    def profitableSchemes(
        self,
        n: int,
        minProfit: int,
        group: List[int],
        profit: List[int]
    ) -> int:
        
        MOD = 10**9 + 7
        
        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        
        for required_members, earned_profit in zip(group, profit):
            
            for members in range(n, required_members - 1, -1):
                for current_profit in range(minProfit, -1, -1):
                    
                    previous_members = members - required_members
                    
                    new_profit = min(
                        minProfit,
                        current_profit + earned_profit
                    )
                    
                    dp[members][new_profit] = (
                        dp[members][new_profit]
                        + dp[previous_members][current_profit]
                    ) % MOD
        
        answer = 0
        
        for members in range(n + 1):
            answer = (answer + dp[members][minProfit]) % MOD
        
        return answer

The implementation begins by creating a 2D DP table indexed by member count and profit level.

The base case:

dp[0][0] = 1

represents the empty subset.

For every crime, we iterate backward through possible member counts and profits. Backward iteration is essential because it prevents the same crime from being reused multiple times during a single iteration.

The transition adds the current crime to previously reachable states. Profit is capped using:

min(minProfit, current_profit + earned_profit)

which keeps the DP table bounded.

Finally, we sum all states whose profit index equals minProfit, since that represents all schemes achieving at least the required profit.

Go Solution

func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	const MOD int = 1000000007

	dp := make([][]int, n+1)

	for i := 0; i <= n; i++ {
		dp[i] = make([]int, minProfit+1)
	}

	dp[0][0] = 1

	for i := 0; i < len(group); i++ {
		requiredMembers := group[i]
		earnedProfit := profit[i]

		for members := n; members >= requiredMembers; members-- {
			for currentProfit := minProfit; currentProfit >= 0; currentProfit-- {

				previousMembers := members - requiredMembers

				newProfit := currentProfit + earnedProfit
				if newProfit > minProfit {
					newProfit = minProfit
				}

				dp[members][newProfit] =
					(dp[members][newProfit] +
						dp[previousMembers][currentProfit]) % MOD
			}
		}
	}

	answer := 0

	for members := 0; members <= n; members++ {
		answer = (answer + dp[members][minProfit]) % MOD
	}

	return answer
}

The Go implementation mirrors the Python solution closely.

Go uses slices for the DP table, and integer overflow is avoided because all operations are reduced modulo 1e9 + 7.

Unlike Python, Go requires explicit initialization of the 2D slice structure.

Backward iteration logic remains identical and is equally important for correctness.

Worked Examples

Example 1

n = 5
minProfit = 3
group = [2, 2]
profit = [2, 3]

Initial DP state:

Members Profit 0 Profit 1 Profit 2 Profit 3
0 1 0 0 0

Process Crime 0

Crime:

members = 2
profit = 2

Transition from:

dp[0][0] = 1

to:

dp[2][2] += 1

DP now contains:

Members Profit 0 Profit 1 Profit 2 Profit 3
0 1 0 0 0
2 0 0 1 0

Process Crime 1

Crime:

members = 2
profit = 3

From dp[0][0]:

dp[2][3] += 1

From dp[2][2]:

dp[4][3] += 1

Final valid states:

Members Profit 3
2 1
4 1

Total answer:

2

The two schemes are:

{crime 1}
{crime 0, crime 1}

Example 2

n = 10
minProfit = 5
group = [2,3,5]
profit = [6,7,8]

Every single crime individually already reaches the required profit.

Valid subsets:

Subset Members Used Profit
(0) 2 6
(1) 3 7
(2) 5 8
(0,1) 5 13
(0,2) 7 14
(1,2) 8 15
(0,1,2) 10 21

Total valid schemes:

7

Complexity Analysis

Measure Complexity Explanation
Time O(m * n * minProfit) We process every crime across all member and profit states
Space O(n * minProfit) The DP table stores states for members and capped profit

Here:

  • m = len(group)
  • n is maximum members
  • minProfit is capped at 100

The DP table size is manageable because both dimensions are small. The backward iteration allows us to reuse a single DP table instead of requiring a full 3D DP.

Test Cases

from typing import List

class Solution:
    def profitableSchemes(
        self,
        n: int,
        minProfit: int,
        group: List[int],
        profit: List[int]
    ) -> int:
        
        MOD = 10**9 + 7
        
        dp = [[0] * (minProfit + 1) for _ in range(n + 1)]
        dp[0][0] = 1
        
        for required_members, earned_profit in zip(group, profit):
            for members in range(n, required_members - 1, -1):
                for current_profit in range(minProfit, -1, -1):
                    
                    previous_members = members - required_members
                    
                    new_profit = min(
                        minProfit,
                        current_profit + earned_profit
                    )
                    
                    dp[members][new_profit] = (
                        dp[members][new_profit]
                        + dp[previous_members][current_profit]
                    ) % MOD
        
        return sum(dp[m][minProfit] for m in range(n + 1)) % MOD

solution = Solution()

assert solution.profitableSchemes(
    5, 3, [2, 2], [2, 3]
) == 2  # Example 1

assert solution.profitableSchemes(
    10, 5, [2, 3, 5], [6, 7, 8]
) == 7  # Example 2

assert solution.profitableSchemes(
    1, 1, [1], [1]
) == 1  # Single exact-fit crime

assert solution.profitableSchemes(
    1, 2, [1], [1]
) == 0  # Impossible to reach profit

assert solution.profitableSchemes(
    5, 0, [1, 2], [0, 0]
) == 4  # Empty subset plus all combinations

assert solution.profitableSchemes(
    5, 3, [6], [10]
) == 0  # Crime exceeds member limit

assert solution.profitableSchemes(
    5, 5, [2, 2, 1], [2, 3, 1]
) == 3  # Multiple valid combinations

assert solution.profitableSchemes(
    100, 100, [1] * 100, [1] * 100
) == 1  # Must select all crimes

assert solution.profitableSchemes(
    100, 0, [1] * 100, [0] * 100
) == pow(2, 100, 10**9 + 7)  # Every subset valid
Test Why
Example 1 Verifies basic subset counting
Example 2 Verifies multiple combinations
Single exact-fit crime Tests simplest successful case
Impossible profit Tests unreachable target
minProfit = 0 Ensures empty subset counted
Crime exceeds limit Ensures invalid crimes ignored
Multiple valid combinations Tests overlapping DP states
Must select all crimes Tests upper boundary
Every subset valid Stress test for combinatorial explosion

Edge Cases

One important edge case occurs when minProfit = 0. In this scenario, even the empty subset is considered profitable because earning at least zero profit is always satisfied. Many incorrect implementations forget to count the empty scheme. This implementation handles it naturally through the base initialization:

dp[0][0] = 1

Another tricky case occurs when a crime requires more members than available. For example:

n = 5
group[i] = 6

Such a crime can never be selected. The backward member iteration:

for members in range(n, required_members - 1, -1):

automatically skips impossible transitions.

A third important edge case involves profits larger than minProfit. Suppose:

minProfit = 5
current profit = 4
crime profit = 10

The new profit becomes 14, but we do not need separate states for 6, 7, 8, and so on. All of them are equivalent because they already satisfy the requirement. The implementation correctly caps profits using:

min(minProfit, current_profit + earned_profit)

which keeps the DP table compact and prevents unnecessary state explosion.

Another subtle issue is avoiding reuse of the same crime multiple times. If we iterated forward instead of backward, newly updated states could immediately be reused in the same iteration, effectively allowing unlimited usage of a crime. Backward iteration guarantees each crime is counted at most once per scheme.