2

I know that the title I mentioned evokes many other topics already mentioned here (like library itertools) but none could give me a solution. My problem is not complicated to understand. I have 2 digits (say 1 and 2) and I want to put them in a list so that the sum of the numbers in the list gives me a number (say 5) and I need to know all possible combinations from this list there. For example :

a = 1
b = 2
L = [1, 2, 2] -> 5
L = [1, 1, 1, 1, 1] -> 5
L = [1, 1, 1, 2] -> 5
.
.
.

I hope to have been able to describe my problem, it's been more than 2 days that I ream disappointed.

Good day to all

wim
  • 338,267
  • 99
  • 616
  • 750
kevin
  • 33
  • 4
  • Classic problem. Search for "subset sum". Possible duplicate: https://stackoverflow.com/q/46942681/674039 – wim Dec 09 '19 at 03:38
  • I looked and it's not all the same problem as the one I'm asking. In the link solution from above, we do not find the result with any sequence of numbers as described in my question. – kevin Dec 09 '19 at 20:34
  • I still think it's approximately the same problem... anyway added an answer showing how to adapt that algorithm for your use case. – wim Dec 09 '19 at 21:32

1 Answers1

3

With a slight modification of the idea I showed in the proposed duplicate:

from collections import Counter

def subset_sum(vals, target):
    counts = [[Counter()]] + [[] for _ in range(target)]
    for val in vals:
        for i in range(val, target + 1):
            counts[i] += [c + Counter({val: 1}) for c in counts[i-val]]
    return counts[target]

This gives the result:

>>> for counts in subset_sum(vals=(1, 2), target=5):
...     L = [*counts.elements()]
...     print(L, "->", sum(L))
[1, 1, 1, 1, 1] -> 5
[1, 1, 1, 2] -> 5
[1, 2, 2] -> 5
wim
  • 338,267
  • 99
  • 616
  • 750
  • Great! Thank you, it responds perfectly and it has unlocked my exercise. Thank you very much – kevin Dec 09 '19 at 21:42