Most Items for an Exact Weight

Medium

You want to pack items whose total weight is exactly goal. The item weights are listed in weights, and each item can be taken at most once. Return the largest number of items you can take so that their total weight equals goal. If no selection reaches exactly goal, return -1.

Example 1

weights=[6, 2, 3, 1, 4], goal=6 → 3

Sets adding up to 6 include [6], [2, 4] and [2, 3, 1]; the largest of them, [2, 3, 1], has three items.

Example 2

weights=[5, 7], goal=6 → -1

No set of items adds up to exactly 6, so the answer is -1.

Example 3

weights=[2, 2, 2, 2], goal=4 → 2

Constraints

1 ≤ len(weights) ≤ 1000
1 ≤ weights[i] ≤ 1000
1 ≤ goal ≤ 1000

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming

Similar problems

Fewest Jumps to the End Medium Most Profitable Streak Medium Reach the Last Cell Medium Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium

Input

weights=[6, 2, 3, 1, 4], goal=6

Expected

Run checks the first 3 tests in your browser. Submit checks all 95 tests on the server, hidden ones included.