Weight-Only knapsack
Prereqs: 0/1 Knapsack
Given a list of weights of n items, find all sums that can be formed using their weights.
Input & Output
Input
weights — A list of `n` positive integers, representing weights of the items
Output
A list, in any order, of the unique sums that can be obtained by using combinations of the provided weights
Example
Input
weights = [1, 3, 3, 5]
Output
[0, 1, 3, 4, 5, 6, 7, 8, 9, 11, 12]
Explanation
We can form all sums from 0 to 12 except 2 and 10. Here is a short explanation for the sums:
- 0: use none of the weights
- 1: use item with weight 1
- 3: use item with weight 3
- 4: use weights 1 + 3 = 4
- 5: use item with weight 5
- 6: use weights 3 + 3 = 6
- 7: use weights 1 + 3 + 3 = 7
- 8: use weights 3 + 5 = 8
- 9: use weights 1 + 3 + 5 = 9
- 11: use weights 3 + 3 + 5 = 11
- 12: use all weights
Constraints
1 <= len(weights) <= 1001 <= weights[i] <= 100