How to get the target by adding using python

Question

I have one list and one target number.

• I need to print the number of ways to reach target

l = [1,2,3]

target = 5

Number of ways is below

• 1+ 1 + 1 + 1 + 1 = 5
• 1 + 1 + 1+ 2 =5
• 1 + 2 + 2 = 5
• 1 +1 +3 =5
• 2 + 3 = 5

Output 5 ways

def countways(l, target ):

    if (target  == 0):
        return 0
    else:
        pass
if __name__ == "__main__":
     l = [1,2,3], 
     target = 5
     countways(l, target )

Can we do it using native python or itertools?

Answer 1

I will assume all numbers are positive.

You can use itertools to check all combinations_with_replacement, as proposed by Ann, but it will get unnecessarily slow for large inputs as there are exponentially many combinations.

Naive recursive approach

This version uses the recursion approach Nevetha described, which allows to early-return out of branches where no matches will ever be found, but should do it with replacement.

As with the other results: It is fairly easy to extend to print the actual summands. We would simply add an optional, third parameter that gives the summands so far, and print it in the target == 0 case.

def countWays(elements, target):
    if target < 0:
        return 0

    if target == 0:
        return 1

    total = 0
    for index, element in enumerate(elements):
       total += countWays(elements[index:], target - element)
 
    return total
 
 
if __name__ == '__main__':
    print(countWays([1, 2, 3], 5))
    print(countWays([5, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40], 30))
    print(countWays([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37], 40))
    print(countWays([1, 2, 3, 4, 5], 200))

DP algorithm

As you can see, for the target of 200, this already takes quite some time to execute. This is because at the end of the recursion, we always only add one to our result. This can be improved by using dynamic programming -- either by simply adding caching (example code, of course the global variable shouldn't be used in any real program):

cache = {}
def countWays(elements, target):
    global cache

    if target < 0:
        return 0

    if target == 0:
        return 1

    cache_key = (tuple(elements), target)
    if cache_key in cache:
        return cache[cache_key]

    total = 0
    for index, element in enumerate(elements):
       total += countWays(elements[index:], target - element)

    cache[cache_key] = total
    return total

or by directly building the dp array as already discussed here:

def countWays(elements, target):   
    dp = [1] + [0] * target
    for element in elements:
        for i in range(0, target - element + 1):
            dp[i + element] += dp[i]
    return dp[target]

Answer 2

You can use the itertools.combinations_with_replacement() method:

from itertools import combinations_with_replacement as cwr

def countways(l, target):
    return len([1 for i in range(target) for j in cwr(l, i + 1) if sum(j) == target])

print(countways([1, 2, 3], 5))

Output:

5

---

Explanation

The docstring for the method is as follows:

Return r length subsequences of elements from the input iterable allowing individual elements to be repeated more than once.

So it's like the itertools.combinations() method, expect that the itertools.combinations_with_replacement() method allows elements to be repeated.

If you want to visualize the different solutions:

from itertools import combinations_with_replacement as cwr

def countways(l, target):
    for i in range(target):
        for j in cwr(l, i + 1):
            if sum(j) == target:
                print(j)

countways([1, 2, 3], 5)

Output:

(2, 3)
(1, 1, 3)
(1, 2, 2)
(1, 1, 1, 2)
(1, 1, 1, 1, 1)

---

Note: This can be very slow for large inputs, as pointed out by @He3lixxx (+1). You can improve the efficiency by filtering out numbers in l that are greater than target, and by dividing the target in range(target) by max(l) and min(l), like so:

def countways(l, target):
    l = [i for i in l if i <= target]
    return len([1 for i in range(target // max(l) - 1,
                                 target // min(l)) for j in cwr(l, i + 1) if sum(j) == target])

Answer 3

A dynamic programming approach will work. This code outputs all the possible combinations possible. Just print the length of the list to get the total counts. Also, all the possible combinations are unique and don't repeat.

def ways(l, target):
    dp =[ [] for i in range(target+1) ]
    l.sort()
    n=len(l)
    for i in range(n):
        for j in range(l[i], target+1):    
            if j==l[i]:
                dp[j].append([l[i]])
            else:
                if dp[j-l[i]]:   
                    for u in dp[j-l[i]]:       
                        dp[j].append(u+[l[i]])       
    return dp[-1]

if __name__ == "__main__":
     l = [1,2,3] 
     target = 5
     print(len(ways(l, target)))
     l = [5, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40]
     target = 30
     print(len(ways(l, target)))

Answer 4

You can resolve using itertools like the example below:

import itertools 

def countways(l, target): 
    data = []  
    for length in range(1, target+1):  
        data.extend([x for x in itertools.combinations_with_replacement(l, length) if sum(x) == target]) 
    return len(data)

You need to create combinations with all the sizes between 1 and target so the for is necessary. In each iteration you save the combinations with the sum values equal target. In the end you just need to count the saved lists.