Skip to content
RED SAGSkills
medium30 ptsbacktrackingsorting

Spend the Budget Exactly

You have a list of item prices candidates (positive integers, possibly repeated) and a target budget. Find every distinct combination of items whose prices add up to exactly target. Each item in the list can be used at most once.

Each combination must be sorted in ascending order, and the same combination of prices must not appear twice. The combinations may be returned in any order.

Example 1

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

Example 2

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]

Constraints

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
Hint 1

Sort the prices first so you can stop early once a price exceeds what is left.

Hint 2

At each depth, skip a price equal to the previous one you tried at that same depth; that removes duplicate combinations.

Discussion 0

Join free to post in the discussion.

Good practice for: Backend Developer, Full Stack Developer, Data Scientist, Automation Test Engineer, Game Developer

Run checks your code on 3 sample tests. Submit runs all 8 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.