You have a bag of positive whole numbers. Can you pick some of them, each at most once, so that the picked numbers add up to exactly target?
Implement can_make(nums: list[int], target: int) -> bool.
can_make([4, 9, 2, 6], 15) # True 9 + 6 (or 4 + 9 + 2)
can_make([4, 9, 2, 6], 14) # False no subset works
can_make([5], 10) # False the single 5 can't be used twice
Picking nothing is allowed, so target == 0 is always True.
Constraints: 0 <= len(nums) <= 100, 1 <= nums[i] <= 1000, 0 <= target <= 10_000. Trying all 2^n subsets is hopeless at n = 100.
Show hint
keep reachable[s] = "some subset of the numbers seen so far sums to s", and for each number loop s from target down to that number, so a number can't build on a sum it already helped make.