Determine if you can make change with N denominations using each denomination only once and with at most k coins

Question

This is a version of the coin-changing problem. As such, it is a dynamic programming problem.

I know how to determine if you can make change if either you can use at most one coin of each denomination or if you can use at most k coins, but not both.

Answer 1

Combining the constraints is fairly straightforward. We can build a three-dimensional table with dimensions representing maximum coin allowed, number of coins allowed, and target sum, or we can just say "screw it" and throw memoization on top of a straightforward recursive solution. In Python:

# Assume we have a memoization decorator.
# functools.lru_cache(maxsize=None) would do.
@memoize
def knapsack_possible(coin_tuple, target, k):
    if not target:
        # Target achieved.
        return True
    elif not coin_tuple or not k:
        # Out of coins.
        return False
    else:
        return (knapsack_possible(coin_tuple[:-1], target, k) or
                knapsack_possible(coin_tuple[:-1], target-coin_list[-1], k-1)