Must use Recursion

I want to find the distinct tuples whose sum equals to K, from an input list with no repeated numbers. I have to do this without using functions from Python's library, such as functions from itertools. Any solution also has to use recursive algorithms.

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...

CodePudding user response：

A naive approach would be to:

1. Generate all combinations of 1, 2, ... n numbers
2. Filter which combinations have a sum == K
3. Generate all the permutations of these combinations (this step seems useless, because sum is commutative, but I'm assuming that is the definition of your problem)

Note that this is an instance of the Subset Sum Problem, which is a difficult optimisation problem. The solution below does not scale well for large sets.

The itertools module gives you two very useful functions, combinations and permutations, that simplify steps 1 and 3 above. Note that the code below assumes only strictly positive numbers (i.e. larger than 0). If a negative or zero is used, the results will be incorrect.

from itertools import combinations, permutations

def generate_all_combinations(numbers, target_sum):
    # Micro-optimisation: filter numbers that are smaller or equal to target_sum
    result = []
    if target_sum in numbers:
        result.append((target_sum,))
    number_set = set(n for n in numbers if n < target_sum)
    for i in range(2, len(number_set)   1):  # Loop through all combination sizes
        result.extend(comb for comb in combinations(number_set, i) if sum(comb) == target_sum)
    return result

def expand_with_permutations(combinations):
    expanded_result = []
    for comb in combinations:
        expanded_result.extend(permutations(comb))
    return expanded_result

def print_results(results):
    for el in results:
        print(el)

# Input:
a = [1,2,3,4,6,7,8]
k = 8
all_combinations = generate_all_combinations(a, k)
all_permutations = expand_with_permutations(all_combinations)
print_results(all_permutations)

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

CodePudding user response：

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)

CodePudding user response：

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)]