Subset Sum with Backtracking on Python

Question

So I want to print out all the subsets of the initial set that will add up to 21. So far I've only come up with this

def twentyone(array, num=21):
    if len(array) == 0:
        return None
    else:
        if array[0] == num:
            return [array[0]]
        else:
            with_v = twentyone(array[1:], (num - array[0]))
            if with_v:
                return [array[0]] + with_v
            else:
                return twentyone(array[1:], num)

It does give the solution, but only the first. How do I change it so that it will give me every possible subset. I've tried making a few changes but it only gives me nested lists. Any help would be nice.

JuniorCompressor · Accepted Answer · 2015-04-05 12:05:38Z

4

You can create a recursive generator:

def twentyone(array, num=21):
    if num < 0:
        return
    if len(array) == 0:
        if num == 0:
            yield []
        return
    for solution in twentyone(array[1:], num):
        yield solution
    for solution in twentyone(array[1:], num - array[0]):
        yield [array[0]] + solution

Example:

>>> list(twentyone([5, 16, 3, 2]))
[[16, 3, 2], [5, 16]]

edited Apr 5, 2015 at 12:05

answered Apr 5, 2015 at 11:04

JuniorCompressor

20.1k4 gold badges33 silver badges58 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Rylai Crestfall Over a year ago

your answer is right. however, how do i improve the runtime if i have an input such as. the one below. I've been told to do simple pruning. How do i take out the solutions that are already present? seq = [10] + [22]*50 + [11] print(sorted(twentyone(seq))) @JuniorCompressor

Selcuk · Accepted Answer · 2015-04-05 11:00:45Z

1

If you are allowed to use standard Python libraries, here is a shorter solution:

import itertools
import operator


def twentyone(array, num=21):
    subsets = reduce(operator.add, [list(itertools.combinations(array, r)) for r in range(1, 1 + len(array))])
    return [subset for subset in subsets if sum(subset) == num]


print twentyone([1, 2, 5, 6, 8, 9, 10])

result:

[(2, 9, 10), (5, 6, 10), (1, 2, 8, 10), (1, 5, 6, 9), (2, 5, 6, 8)]

answered Apr 5, 2015 at 11:00

Selcuk

60.1k12 gold badges114 silver badges119 bronze badges

2 Comments

thefourtheye Over a year ago

This is highly inefficient and OP has tagged recursion and backtracking specifically.

Selcuk Over a year ago

@thefourtheye Fair enough, not backtracking but this solution is recursive too.

Collectives™ on Stack Overflow

Subset Sum with Backtracking on Python

2 Answers 2

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related