Clarify question "Sum to N" problem in Python Basics

[levon003]

Just a small tweak to an underspecified question. The question is substantially harder and substantially less likely to have valid finite answers if negative integers are permissible.

I'll note I wrote a non-recursive implementation with reduced memory usage that could be included as well, if desired.

I also have an answer to the "all integers allowed" case, but it's not very elegant so I recommend just tweaking the question to specify positive integers.

[dipranjan]

Thank you for sharing this. Please share the non-recursive implementation too, I will include it.

[levon003]

Not a very good implementation, but here it is:

def sum_combinations_with_replacement(integer_list, target_value):
    assert all([integer > 0 for integer in integer_list]), "Positive integers required."
    # for each combination, we need to store: 
    # current index in integer_list, the current total, and the current times each term is included
    possible_combinations = [
        [0, 0, {}]
    ]
    valid_combinations = set()
    while len(possible_combinations) > 0:
        new_combinations = []
        for idx, total, count_dict in possible_combinations:
            if total == target_value:
                # this is a valid combination,
                # so convert from the sparse representation of term counts to a full list
                result_list = []
                for integer, count in count_dict.items():
                    result_list.extend([integer,] * count)
                valid_combinations.add(tuple(sorted(result_list)))
            elif total < target_value:
                # not yet at the target, generate new candidate combinations for each integer.
                # only need to consider adding integers at our current index in the integer_list and beyond
                # (since a different root combination will explore the other indices)
                for new_idx in range(idx, len(integer_list)):
                    # keep a running total to avoid redundant calls to sum()
                    new_total = total + integer_to_add
                    # copy the current formula (in a dictionary of integers -> counts)
                    # and add 1 to the count of whichever integer we're adding for this candidate
                    new_count_dict = count_dict.copy()
                    integer_to_add = integer_list[new_idx]
                    if integer_to_add not in new_count_dict:
                        new_count_dict[integer_to_add] = 0
                    new_count_dict[integer_to_add] += 1
                    combination = (new_idx, new_total, new_count_dict)
                    new_combinations.append(combination)
            # else: the total exceeds the target value
        possible_combinations = new_combinations
    return valid_combinations

integers = [2, 3, 5]
target = 8
expected_output = {(2, 2, 2, 2), (2, 3, 3), (3, 5)}
output = sum_combinations_with_replacement(integers, target)
assert expected_output == output

It has the benefit of being faster and using less memory (due to the sparse formula representation, avoiding recursion, and avoiding redundant summing by keeping a running total), but it has the downside of being significantly more verbose.