One-Shot Budget Picks
MediumBacktracking
Problem
A team has a list of task estimates costs (in hours); several tasks may share the same estimate. A sprint has exactly budget hours.
Return every distinct multiset of estimates, using each task at most once, that adds up to exactly budget. Combinations are compared as multisets, so each must appear once. Return them in any order.
Example 1
- Input:
- costs = [10, 1, 2, 7, 6, 1, 5], budget = 8
- Output:
- [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
[1, 7] can be built with either 1-hour task, but it is the same multiset and is listed once.
Example 2
- Input:
- costs = [2, 5, 2, 1, 2], budget = 5
- Output:
- [[1, 2, 2], [5]]
Constraints
- 1 ≤ costs.length ≤ 100
- 1 ≤ costs[i] ≤ 50
- 1 ≤ budget ≤ 30
Hint
Show the first hint
Two ideas from earlier problems combine here: canonical order to avoid reorderings, and skipping equal values to avoid duplicate multisets.
Walkthrough
How to approach it
01Clarify before coding
- Can a task be used twice? No, each index at most once.
- Do equal estimates make different answers? No, [1, 7] is one answer whichever 1 is used.
- What if nothing fits? Return [].
02Brute force
Enumerate all 2^n subsets of tasks, keep those summing to budget, sort each and deduplicate with a set.
Cost: O(n · 2^n): for 100 tasks, 2^100 subsets is hopeless. The last hidden test (100 tasks of 1 hour) breaks it immediately.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.