See all coding puzzles and patterns here.

Problem Definition

Given an array of numbers and a number $k$, determine if a sequence of numbers in the array adds up to $k$. Numbers in the array can only be used once.

Examples

Some test cases to verify our solution.

assert knap([1, 1, 1, 4, 5], 9)
assert knap([1, 1, 1, 4, 5], 7)
assert not knap([1, 1, 4, 5], 8)
assert not knap([1, 1, 1, 4, 5], 100)

Solution

def knap(arr, k):
    ans = [0] * (k + 1)
    ans[0] = 1
    for num in arr:
        # We must iterate backwards over the array so that we don't repeatedly add the current num to an entry
        for idx in range(len(ans) - 1, -1, -1):
            if ans[idx] > 0:
                new_sum = idx + num
                if new_sum < len(ans):
                    ans[new_sum] += ans[idx]
    return ans[k] > 0

Complexity

Let $n = $ len(arr).

Runtime complexity should be $\Theta(n \cdot k)$.

Auxiliary space complexity should also be $\Theta(n \cdot k)$.