101companies

Headline

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

        head = available[0]
        tail = available[1:]
        
        # Skip head
        if currentSum + promise - head >= target:
            recurse(selected, currentSum, tail, promise - head)

        # Recursion while selecting head of available numbers
        selected.append(head)
        recurse(selected, currentSum + head, tail, promise - head)
        selected.pop()

    recurse([], 0, values, sum(values))
    return solutions
Ralf Lämmel edited this article at Tue, 12 May 2020 16:03:35 +0200
(C) 2012-2024 softlang.org and contributors
Compare revisions Compare revisions

User contributions

    This user never has never made submissions.

    User edits

    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.