Efficient way to find partial permutations of list equal to a specific sum

Here is a recursive solution. The efficiency gains depend on:

• Inside the recursive call, do not iterate over the whole list, just the remaining portion of the list.

• No need to fully sum every combination from scratch in order to test it, just subtract off the value from target as you iterate.

A further efficiency gain is possible in this case, relying on the fact that the list only contains positive numbers, so if a particular value would overshot the target then you do not need to make the recursive call (the elif val < target test). Without this fact, that part of the code would need to be unconditional, and then it would take longer.

The test case took 0.04 seconds on an oldish machine.

def yield_combos(N, num, target):
    for i, val in enumerate(N):
        if num == 1:
            if val == target:
                yield [val]
        elif val < target:
            for j in yield_combos(N[i:], num - 1, target - val):
                yield [val] + j
    

N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
target = 20
num = 8
                    
for combo in yield_combos(N, num, target):
    print(f"combo={combo} length={len(combo)} total={sum(combo)}")

This gives:

combo=[0.5, 0.5, 0.5, 0.5, 0.5, 0.5, 2, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 1, 1.5, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2, 3, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 2.5, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 5, 10] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 2.5, 7.5, 7.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 0.5, 5, 5, 7.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 1, 1, 15] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 1.5, 3, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 2.5, 12.5] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 5, 10] length=8 total=20.0
combo=[0.5, 0.5, 0.5, 0.5, 1, 2, 7.5, 7.5] length=8 total=20.0
... etc ...

The above is on the basis that it is permissible to repeat elements. If not, then use N[i+1:] instead of N[i:] in the recursive call, although in that case there are no solutions for target 20.

Note also that this gives each solution only in order of increasing index in the input list (in this case increasing value because the input list happens to be sorted), rather than every permutation of them, based on the understanding that extra permutations are "duplicate values" that the question implies should be avoided. However, if additionally permutations are required, then the efficient thing to do would be do the search initially exactly as above (not loop over the entire list in the recursive call), but then permute only the elements of the solutions as a final step.

import itertools

def func(list, size_perm, target):
     #Generate all permutations
     perms = itertools.permutations(list, size_perm)
     
     #iterate of all permutations and print only if sum == target
     for item in perms:
         if sum(item) == target:
             print(item)
N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
func(N, 8, 20)

Not too sure if this is the most efficient method, but this should work. Let me know if it doesn't work.

The easiest way is using itertools and list comprehension:

import itertools

# Inputs
N = [0.5, 0.8, 1, 1.5, 2, 2.5, 3, 5, 7.5, 10, 12.5, 15, 17.5, 20, 25, 30]
target = 20

# Operation
list_sum=[item for item in itertools.product(N, repeat=8) if sum(item)==target]

# Printing
print(list_sum)

To see the kind of output you get, if you use 2 elements only, the following output is obtained:

[(2.5, 17.5), (5, 15), (7.5, 12.5), (10, 10), (12.5, 7.5), (15, 5), (17.5, 2.5)]

This is not the fastest solution (a recursive function is more optimal). Note that I provide all the possible permutations since I have assumed that the order of the elements may be important. Otherwise, the execution time can be reduced.