Given a list of numbers, how many different ways can you add them together to get a sum S?

Question

Given a list of numbers, how many different ways can you add them together to get a sum S?

Example:

list = [1, 2]

S = 5

1) 1+1+1+1+1 = 5

2) 1+1+1+2 = 5

3) 1+2+2 = 5

4) 2+1+1+1 = 5

5) 2+2+1 = 5

6) 1+2+1+1 = 5

7) 1+1+2+1 = 5

8) 2+1+2 = 5

Answer = 8

This is what I've tried, but it only outputs 3 as the answer

lst = [1, 2]
i = 1
result = 0
while i <= 5:
    s_list = [sum(comb) for comb in combinations_with_replacement(lst, i)]
    for val in s_list:
        if val == 5:
            result += 1
    i+= 1

print(result)

However, this outputs three. I believe it outputs three because it doesn't account for the different order you can add the numbers in. Any ideas on how to solve this.

The problem should work for much larger data: however, I give this simple example to give the general idea.

Answer 1

Use Dynamic Programming.

We suppose that your list consists of [1,2,5] so we have this recursive function :

f(n,[1,2,5]) = f(n-1,[1,2,5]) + f(n-2,[1,2,5]) + f(n-5,[1,2,5])

Because if the first number in sum is 1 then you have f(n-1,[1,2,5]) options for the rest and if it is 2 you have f(n-2,[1,2,5]) option for the rest and so on ...

so start from f(1) and work your way up with Dynamic programming. this solution in the worst case is O(n^2) and this happens when your list has O(n) items.

Solution would be something like this:

answers = []
lst = [1,2]
number = 5
def f(target):
  val = 0
  for i in lst:               #O(lst.count())
    current = target - i
    if current > 0:
      val += answers[current-1]
  if lst.__contains__(target): #O(lst.count())
    val += 1
  answers.insert(target,val)

j = 1;
while j<=number:  #O(n) for while loop
  f(j)
  j+=1

print(answers[number-1])

here is a working version.

Answer 2

How about using dynamic programming? I believe it's more easy to understand and can be implemented easily.

def cal(target, choices, record):

    min_choice = min(choices)
    if min_choice > target:
        return False

    for i in range(0, target+1):
        if i == 0:
            record.append(1)
        elif i < min_choice:
            record.append(0)
        elif i == min_choice:
            record.append(1)
        else:
            num_solution = 0
            j = 0
            while j < len(choices) and i-choices[j] >= 0:
                num_solution += record[i-choices[j]]
                j += 1
            record.append(num_solution)


choices = [1, 2]
record = []
cal(5, choices, record)
print(record)
print(f"Answer:{record[-1]}")

The core idea here is using an extra record array to record how many ways can be found to get current num, e.g. record[2] = 2 means we can use to ways to get a sum of 2 (1+1 or 2).

And we have record[target] = sum(record[target-choices[i]]) where i iterates over choices. Try to think, the way of getting sum=5 must be related with the way of getting sum=4 and so on.

Answer 3

Combinations with the elements in a different order are considered to equivalent. For example, #3 and #5 from your list of summations are considered equivalent if you are only talking about combinations.

In contrast, permutations consider the two collections unique if they are comprised of the same elements in a different order.

To get the answer you are looking for you need to combine both concepts.

1. First, use your technique to find combinations that meet your criteria
2. Next, permute the collection of number from the combination
3. Finally, collect the generated permutations in a set to remove duplicates.

[ins] In [01]: def combination_generator(numbers, k, target):
          ...:     assert k > 0, "Must be a positive number; 'k = {}".format(k)
          ...:     assert len(numbers) > 0, "List of numbers must have at least one element"
          ...:
          ...:     for candidate in (
          ...:         {'numbers': combination, 'sum': sum(combination)}
          ...:         for num_elements in range(1, k + 1)
          ...:         for combination in itertools.combinations_with_replacement(numbers, num_elements)
          ...:     ):
          ...:         if candidate['sum'] != target:
          ...:             continue
          ...:         for permuted_candidate in itertools.permutations(candidate['numbers']):
          ...:             yield permuted_candidate
          ...:

[ins] In [02]: {candidate for candidate in combination_generator([1, 2], 5, 5)}
Out[02]:
{(1, 1, 1, 1, 1),
 (1, 1, 1, 2),
 (1, 1, 2, 1),
 (1, 2, 1, 1),
 (1, 2, 2),
 (2, 1, 1, 1),
 (2, 1, 2),
 (2, 2, 1)}

Answer 4

Using both itertools.combinations_with_replacement and permutations:

import itertools

l = [1,2]
s = 5

res = []
for i in range(1, s+1):
    for tup in itertools.combinations_with_replacement(l, i):
        if sum(tup) == s:
            res.extend(list(itertools.permutations(tup, i)))
res = list(set(res))

print(res)
[(1, 2, 2),
 (2, 2, 1),
 (1, 1, 2, 1),
 (1, 2, 1, 1),
 (2, 1, 1, 1),
 (1, 1, 1, 2),
 (2, 1, 2),
 (1, 1, 1, 1, 1)]

print(len(res))
# 8

Answer 5

You'd want to use recursion to traverse through each possibility for each stage of addition, and pass back the numbers used once you've reached a number that is equal to the expected.

def find_addend_combinations(sum_value, addend_choices, base=0, history=None):
    if history is None: history = []

    if base == sum_value:
        return tuple(history)
    elif base > sum_value:
        return None
    else:
        results = []
        for v in addend_choices:
            r = find_addend_combinations(sum_value, addend_choices, base + v,
                                         history + [v])
            if isinstance(r, tuple):
                results.append(r)
            elif isinstance(r, list):
                results.extend(r)
        return results

You could write the last part a list comprehension but I think this way is clearer.