Find Distinct parts of List that Sum are equal to the given Number

Question

I want to find the distinct tuples whose sum equals to K, from an input list with no repeated numbers.

Input: A=[1, 2, 3], K = 3 
Output: 
(1, 2)
(2, 1)
(3) 

Note that - (2,3) is not same as (3,2).

What I am doing:

def unique_combination(l, sum, K, local, A):
 
    # If a unique combination is found
    if (sum == K):
        print("(", end="")
        for i in range(len(local)):
            if (i != 0):
                print(" ", end="")
            print(local[i], end="")
            if (i != len(local) - 1):
                print(", ", end="")
        print(")")
        return
 
    # For all other combinations
    for i in range(l, len(A), 1):
 
        # Check if the sum exceeds K
        if (sum + A[i] > K):
            continue
 
        # Check if it is repeated or not
        if (i > l and
                A[i] == A[i - 1]):
            continue
 
        # Take the element into the combination
        local.append(A[i])
 
        # Recursive call
        unique_combination(i+1, sum + A[i],
                           K, local, A)
 
        # Remove element from the combination
        local.remove(local[len(local) - 1])
 

def myFunc(A, K):
 
    # Sort the given elements
    A.sort(reverse=False)
 
    local = []
 
    unique_combination(0, 0, K, local, A)
 

arr = [1,2,3,4,6,7]
target = 8
myFunc(arr, target)

This function Return:

Input: A=[1,2,3,4,6,7], K = 8 
Output: 
(1,  3,  4)
(1,  7)
(2,  6)

I also want the other combination like: (1, 4, 3), (1, 3, 4), (4, 1, 3), (4, 3, 1), (3, 1, 4), (3, 4, 1), (7, 1), (2, 6)

So, What should I do with the code to achieve my result...

Answer 1

Using itertools to go through the candidates:

from itertools import permutations

A = [1,2,3,4,6,7]
K = 8 

for n in range(len(A) + 1):
    for perm in permutations(A, n):
        if sum(perm) == K:
            print(perm)

Output:

(1, 7)
(2, 6)
(6, 2)
(7, 1)
(1, 3, 4)
(1, 4, 3)
(3, 1, 4)
(3, 4, 1)
(4, 1, 3)
(4, 3, 1)

Answer 2

use permutations

from itertools import permutations
k=8
data = [ 1, 2, 3, 4, 5, 6,7]
ans = []
for i in range(len(data)):
    ans.extend([values for values in permutations(data, i+1) if sum(values)==k])

print(ans)

Output:

$ python3 test.py
[(1, 7), (2, 6), (3, 5), (5, 3), (6, 2), (7, 1), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (2, 1, 5), (2, 5, 1), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1), (5, 1, 2), (5, 2, 1)]

One liner solution :

k = 8

data = range(1, 8)

ans = [values for i in range(len(data)) for values in itertools.permutations(data, i+1) if sum(values) ==k]
print('permutations : ', ans)

Output:

permutations :  [(1, 7), (2, 6), (3, 5), (5, 3), (6, 2), (7, 1), (1, 2, 5), (1, 3, 4), (1, 4, 3), (1, 5, 2), (2, 1, 5), (2, 5, 1), (3, 1, 4), (3, 4, 1), (4, 1, 3), (4, 3, 1), (5, 1, 2), (5, 2, 1)]