Given a non-negative amount and a list of positive numbers, return true if it's
possible to add up to exactly amount using the numbers, reusing each number as
many times as you like. amount = 0 is always possible (use nothing).
sumPossible(amount, nums)
Input format: amount | nums.
amount=8, nums=[5, 3, 4, 7] // → true (5+3)
amount=7, nums=[2, 4] // → false
amount=0, nums=[1] // → true
"Can I make this amount using the numbers, with reuse?" has an obvious recursive shape: to make amount, pick some number to use last, then make the smaller leftover amount. So sumPossible(amount) is true exactly when some num makes sumPossible(amount - num) true.
Two things stop the recursion: amount exactly 0 means success. Amount going negative means this branch failed — no positive number can undo an overshoot.
Written straightforwardly, this tries every number at every step. Many different sequences of choices land on the same remaining amount — using 5 then 3, or 3 then 5, leave the same remainder. The naive recursion re-explores that same remaining amount from scratch every time it's reached, even though the answer never changes based on how you got there. That redundancy compounds with depth, producing exponential blowup.
The only thing that matters for the rest of the recursion is the current remaining amount — not which numbers were used or in what order. So the subproblem is fully identified by one value. Once you know whether a remaining amount is achievable, that answer never changes.
Cache from "remaining amount" to "achievable" (true/false). Check before exploring; if cached, return immediately. Otherwise try each number, recurse, and store the result once determined.
Only amount + 1 distinct remaining values can ever come up, so with memoization each is solved at most once, and solving one costs "try every number." Total work is roughly amount × (number of choices) — polynomial instead of exponential. "Subtract a choice, recurse on what's left, cache by what's left" reappears throughout DP wherever repeated, reusable choices toward a target are allowed.
def sum_possible(amount, nums):
memo = {}
def solve_amt(a):
if a == 0:
return True
if a < 0:
return False
if a in memo:
return memo[a]
for num in nums:
if solve_amt(a - num):
memo[a] = True
return True
memo[a] = False
return False
return solve_amt(amount)
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.