Introduction

This problem asks for a subset of exactly K elements whose sum is as large as possible while still staying strictly below M. A brute-force combination search works for small inputs, but if the numbers are non-negative and M is not enormous, a dynamic-programming approach is much more practical.

Brute force is the simplest baseline

The direct approach is to generate every subset of size K, compute its sum, and keep the best one that stays below M.

1from itertools import combinations
2
3def best_subset_sum_bruteforce(values, k, limit):
4    best = None
5    best_subset = None
6
7    for subset in combinations(values, k):
8        total = sum(subset)
9        if total < limit and (best is None or total > best):
10            best = total
11            best_subset = subset
12
13    return best, best_subset
14
15
16print(best_subset_sum_bruteforce([3, 1, 7, 5, 9], 3, 15))

This is easy to understand and useful for verification, but the number of combinations grows quickly.

Dynamic programming works well for non-negative values

If the input values are non-negative integers, you can track which sums are reachable using exactly j chosen elements.

The idea is:

• 'dp[j] stores the set of sums reachable with exactly j picks'
• start from dp[0] = {0}
• for each value, update higher j counts from right to left

1def best_subset_sum_dp(values, k, limit):
2    dp = [set() for _ in range(k + 1)]
3    dp[0].add(0)
4
5    for value in values:
6        for size in range(k, 0, -1):
7            for prev_sum in dp[size - 1]:
8                new_sum = prev_sum + value
9                if new_sum < limit:
10                    dp[size].add(new_sum)
11
12    return max(dp[k]) if dp[k] else None
13
14
15print(best_subset_sum_dp([3, 1, 7, 5, 9], 3, 15))

For the example input, the best valid sum is 13.

This method is much faster than full combination search when the reachable-sum space stays manageable.

Know what assumptions the DP relies on

This style of DP is most natural when:

• values are integers
• values are non-negative
• the limit M is not absurdly large relative to the reachable sums

If negative values are allowed, the state space becomes more awkward. If n is small but values are huge, brute force or meet-in-the-middle may be a better fit.

So the correct algorithm depends on the shape of the input, not only on the problem statement.

Recovering the actual subset

Sometimes you need the subset itself, not only the best sum. In that case, store predecessor information instead of only reachable sums. One simple way is to map each reachable sum to the tuple that produced it.

1def best_subset_with_trace(values, k, limit):
2    dp = [dict() for _ in range(k + 1)]
3    dp[0][0] = ()
4
5    for value in values:
6        for size in range(k, 0, -1):
7            for prev_sum, subset in list(dp[size - 1].items()):
8                new_sum = prev_sum + value
9                if new_sum < limit and new_sum not in dp[size]:
10                    dp[size][new_sum] = subset + (value,)
11
12    if not dp[k]:
13        return None, None
14
15    best_sum = max(dp[k])
16    return best_sum, dp[k][best_sum]
17
18
19print(best_subset_with_trace([3, 1, 7, 5, 9], 3, 15))

That makes the solution more useful for real selection problems such as budgeting or packing.

Common Pitfalls

• Using a greedy choice such as "take the largest values first" even though the constraint can make that invalid or suboptimal.
• Forgetting that the subset must have exactly K elements, not just at most K.
• Applying the simple sum-based DP blindly when negative values are allowed.
• Treating the brute-force solution as scalable for large n.
• Returning the best sum without checking whether any valid subset of size K exists at all.

Summary

• Brute force is the simplest correct baseline for this problem.
• For non-negative integers, dynamic programming on subset size and reachable sums is usually much better.
• The right state is "reachable sum using exactly j picks."
• If you need the subset itself, store predecessor or trace information.
• Always check whether the input assumptions match the algorithm you chose.