FunctionRacerProblemsRace

Fill the Sack Exactly

EasyDynamic programmingPython, JavaScript, TypeScript, Java, C++

You have a sack that holds exactly capacity kilograms and a pile of stones whose weights are listed in weights. Return true if you can choose some of the stones (each at most once, possibly none at all) so that their weights add up to exactly capacity, and false otherwise. Choosing no stones gives a total of 0, so capacity = 0 is always possible, even with no stones.

Example 1

weights [5,8,3,11]
capacity 14
returns true

3 + 11 = 14.

Example 2

weights [5,8,3,11]
capacity 10
returns false

No selection of 5, 8, 3 and 11 adds up to 10: the nearest totals you can make are 8 and 11.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Dynamic programming problems