find_terms_for_number_in_list.py

from random import randint

def find_components(raw_array, value):
    """
    ~O(n) find first combination in `new_array` which sum equal `value`.    
    """
    
    # remove from array all values grand then needed value
    array = list(filter(lambda x: x <= value, raw_array))
    
    # keep only unique values
    array = list(set(array))
    
    # sort big to small
    array = sorted(array, reverse=True)
    
    for number in array:
        if number == value:
            return [number]
 
        # remove number from array, because if does not exists combinations 
        # with him, then we don't need recombinate it in other cycle
        array.remove(number)

        # get remainder value
        diff = value - number
        
        # copy remainder array
        _copy = list(array)

        # find in remainder array other summ components for that number
        sub_components = find_components(_copy, diff)
        
        if sub_components:
            return [number] + sub_components
    return []

arr = map(lambda x: randint(1, 10000), range(0, 1000))
need = randint(1, 20000)

need_combinations = find_components(list(arr), need)
if need_combinations:
    msg = "for number {} founded combination {} with summ {}"
    print(msg.format(need, need_combinations, sum(need_combinations)))
else:
    print("does not have combinations")