Filtering the duplicates in subset sum combinations

Question

Given an array, I've found all the combinations of subsets that equal a targeted sum, that's because I want the largest array possible.

For instance, the array [1, 2, 2, 2] for the target sum of "4" returns [[2, 2], [2, 2], [2, 2]].

subsets = []

def subset_sum(numbers, target, partial=[]):
    s = sum(partial)
    if s == target:
        subsets.append(partial)
    if s >= target:
        return
    for i in range(len(numbers)):
        n = numbers[i]
        remaining = numbers[i + 1:]
        subset_sum(remaining, target, partial + [n])

subsets.sort()
subsets.reversed()

How can I remove values that are once mentioned in the subsets' list? In the example above, how can I hay only one [2,2].

And that, show the values of the initial array that are not in this final list? In the example above [1].

[Careful of that `partial=[]`](https://stackoverflow.com/questions/1132941/least-astonishment-and-the-mutable-default-argument). If you can refactor your code into returning a tuples, you can return a set of tuples, which will remove duplicates for you. — Patrick Haugh, Dec 05 '17 at 03:21
What I really want is not only removing the subsets the even one of their values has been used before i.e mentioned in the sorted subsets' list. — Elis Mower, Dec 05 '17 at 03:31
@ElisMower I'm not sure what exactly you want here. I posted an answer below, but it seems like you want something different — RoadRunner, Dec 05 '17 at 03:35
For instance: [[2, 2], [1, 3], [1, 3], [1, 3], [1, 3], [1, 1, 2], [1, 1, 2]]. In here, after the first two subsets, I want only [2,2] and [1,3] to remain. — Elis Mower, Dec 05 '17 at 03:35

RoadRunner · Accepted Answer · 2017-12-05T03:48:35.780

You can use itertools.groupby to remove duplicate lists:

>>> import itertools
>>> lst = [[2, 2], [2, 2], [2, 2]]
>>> lst.sort()
>>> new_lst = list(k for k,_ in itertools.groupby(lst))
>>> print(new_lst)
[[2, 2]]

Then simply flatten new_lst with itertools.chain.from_iterable and check if any of the elements from the initial list do not exist in this flattened list:

>>> initial = [1,2,2,2]
>>> print([x for x in initial if x not in itertools.chain.from_iterable(new_lst)])
[1]

Note: You can probably make your subset_sum() return a list of non duplicate items also, but the above should also work fine.

score 0 · Answer 2 · answered Dec 05 '17 at 03:51

This is not a direct answer to your question, but a better algorithm. If you're only looking for one example of a list of maximal length which satisfies your sum criterion, you should be looking at longer lists first. This code uses itertools for the combinatorial bits and will stop when the longest list is found.

numbers = [1, 2, 2, 2]
taget = 5

for size in reversed(range(1, 1 + len(numbers))):
    for c in itertools.combinations(numbers, size):
        if sum(c) == target:
            break
    else:
        continue
    break

c now contains the longest subset as a tuple (1, 2, 2)

score 0 · Answer 3 · answered Dec 05 '17 at 04:29

You can do something like this:

Data is :

data=[1, 2, 2,2]
import itertools
your_target=4

One line solution:

print(set([k for k in itertools.combinations(data,r=2) if sum(k)==your_target]))

output:

{(2, 2)}

or better if you use a function:

def targeted_sum(data,your_target):
    result=set([k for k in itertools.combinations(data,r=2) if sum(k)==your_target])
    return result

print(targeted_sum(data,4))

Filtering the duplicates in subset sum combinations

3 Answers3