DumbTest.py

# encoding=utf-8
__author__ = "Quazi Nafiul Islam"

from bisect import *
from array import array


def find_le(a, x):
    """Find rightmost value less than or equal to x"""
    i = bisect_right(a, x)
    return a[i - 1] if i else None


def search(n, l):
    found = find_le(l, n)

    if found:
        if found == n or n == 0:
            return True
        else:
            i = l.index(found)
            if search(n - found, l[:i + 1]):
                return True
            else:
                return search(n, l[:i])

    return False


def coin_finder(amount, coins):
    coins *= 2
    coins = array('i', sorted(coins))
    return search(amount, coins)


if __name__ == '__main__':
    print coin_finder(3, array('i', [2, 5]))
    print coin_finder(3, array('i', [1, 2]))
    print coin_finder(3, array('i', [2, 10]))
    print coin_finder(3, array('i', [1, 2]))
    print coin_finder(3, array('i', [3, 10]))
    print coin_finder(3, array('i', [1, 3, 5]))
    print coin_finder(6, array('i', [2, 4, 5]))