Source code for tryalgo.subsetsum
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
subsetsum
jill-jenn vie et christoph durr - 2015-2018
"""
# snip{ subsetsum
[docs]
def subset_sum(x, R):
"""Subsetsum
:param x: table of non negative values
:param R: target value
:returns bool: True if a subset of x sums to R
:complexity: O(n*R)
"""
b = [False] * (R + 1)
b[0] = True
for xi in x:
for s in range(R, xi - 1, -1):
b[s] |= b[s - xi]
return b[R]
# snip}
# snip{ coinchange
[docs]
def coin_change(x, R):
"""Coin change
:param x: table of non negative values
:param R: target value
:returns bool: True if there is a non negative linear combination
of x that has value R
:complexity: O(n*R)
"""
b = [False] * (R + 1)
b[0] = True
for xi in x:
for s in range(xi, R + 1):
b[s] |= b[s - xi]
return b[R]
# snip}