How to decompose a number in a sum of smaller numbers that are provided. Without duplicates (ie order does not matter). Example: decompose 3 in a sum of numbers from [1,2,4]: 1+2 and 1+1+1

unique_combinations.py

sep = '-'
results = []

def decompose(num, operands, path):
    """ Append a valid path to results if it's possible to decompose the num. 
    num = number to decompose,
    operands = list of operands allowed to use in the decomposition,
    path = current chain of operands, string,
    """
    min_operand = operands[-1]

    if num == 0:
        valid_path = path.lstrip(sep)
        results.append(valid_path)

    elif num == min_operand:
        valid_path = sep.join([path, str(min_operand)])
        valid_path = valid_path.lstrip(sep)
        results.append(valid_path)

    elif num > min_operand:
        remaining_operands = operands[:] # copy
        while remaining_operands:
            min_op = remaining_operands[-1]
            new_num = num - min_op
            new_path = sep.join([path, str(min_op)])
            decompose(new_num, remaining_operands, new_path)
            remaining_operands.pop()


ops = [1,2,3]
ops.sort(reverse=True)
decompose(12, ops, '')


for r in results:
    #if r.count('1') < (len(r) - r.count(sep)) / 2 +1:
    print r