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]