# Subset sum problem

The problem of summing up a subset of given numbers to a given target

## Description

There are slightly different formulations, but a simple baseline may be this:

• Input:
• A set x of numbers (e.g., positive integers).
• A target sum s.
• Output:
• A subset y of x which adds up to s.
Variations may be concerned with aspects as follows:
• the type of numbers;
• the constraint whether to met exactly the sum.
The problem is computationally expensive; it's NP-complete.

## Illustration

We use positive decimal numbers below. This choice is motivated by applications that involve money amounts

For example, consider this sample consisting of values to select from and the target sum:

```simple = (
[
Decimal('5.99'),
Decimal('6.53'),
Decimal('11.58'),
Decimal('22.02'),
Decimal('55.32'),
Decimal('58.81'),
Decimal('61.98'),
Decimal('83.07'),
Decimal('240.33'),
],
Decimal('145.05')
)
```

This is the expected solution:

```61.98 + 83.07 = 145.05 ```

### Brute-force iterative solution

This is a brute force solution to the subset-sum problem. We iterate over all pow(2, len(values)) combinations. To this end, we use a list of bits on which we perform all those many increments. We maintain a current sum along the way.

```def solve(values, target):

# Collect solutions in a result list
solutions = []

# Initialize all bits (positions) to False
bits = [False] * len(values)

# Initialize current sum
currentSum = 0

# Loop over all binary numbers  - 1
while True:

if currentSum == target:
selected = [v for i, v in enumerate(values) if bits[i]]
solutions.append(selected)

# Increment bits and adjust current sum along the way.
# We are done once we run out of bits to increment.
pos = 0
while pos < len(values) and bits[pos] == True:
bits[pos] = False
currentSum -= values[pos]
pos += 1
if pos == len(values):
break
else:
bits[pos] = True
currentSum += values[pos]

return solutions
```

### Optimized recursive solution

This is an optimized solution to the subset-sum problem. We use recursion to choose to select any given value or not. We enforce some bounds for opptimization, thereby curtailing recursion.

```def solve(values, target):

# Collect solutions in a result list
solutions = []

values.sort(reverse=True)

def recurse(
selected,  # Elements selected so far
currentSum,  # Sum of selected
available,  # Elements still available for selection
promise,  # Sum of available
):

nonlocal solutions

# Met target!
if currentSum == target:
solutions.append(selected.copy())

# Greater equal target; don't select more numbers
if currentSum >= target:
return

# Nothing left to be selected
if len(available) == 0:
return

tail = available[1:]

if currentSum + promise - head >= target:
recurse(selected, currentSum, tail, promise - head)

# Recursion while selecting head of available numbers
selected.pop()

recurse([], 0, values, sum(values))
return solutions
``` Ralf Lämmel edited this article at Tue, 12 May 2020 16:03:35 +0200

## User contributions

This user never has never made submissions.

## Syntax for editing wiki

For you are available next options:

will make text bold.

will make text italic.

will make text underlined.

will make text striked.

will allow you to paste code headline into the page.

will allow you to link into the page.

will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

will allow you to paste image into the page.

is list with bullets.

is list with numbers.

will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

will allow your to insert code snippets from @worker.

## Syntax for editing wiki

For you are available next options:

will make text bold.

will make text italic.

will make text underlined.

will make text striked.

will allow you to paste code headline into the page.

will allow you to link into the page.

will allow you to paste code with syntax highlight into the page. You will need to define used programming language.

will allow you to paste image into the page.

is list with bullets.

is list with numbers.

will allow your to insert slideshare presentation into the page. You need to copy link to presentation and insert it as parameter in this tag.

will allow your to insert youtube video into the page. You need to copy link to youtube page with video and insert it as parameter in this tag.

will allow your to insert code snippets from @worker.