How to check if a number can be represented as a sum of some given numbers

Question

I've got a list of some integers, e.g. [1, 2, 3, 4, 5, 10] And I've another integer (N). For example, N = 19.

I want to check if my integer can be represented as a sum of any amount of numbers in my list:

19 = 10 + 5 + 4

or

19 = 10 + 4 + 3 + 2

Every number from the list can be used only once. N can raise up to 2 thousand or more. Size of the list can reach 200 integers.

Is there a good way to solve this problem?

Answer 1

4 years and a half later, this question is answered by Jonathan. I want to post two implementations (bruteforce and Jonathan's) in Python and their performance comparison.

def check_sum_bruteforce(numbers, n):
    # This bruteforce approach can be improved (for some cases) by
    # returning True as soon as the needed sum is found;

    sums = []

    for number in numbers:
        for sum_ in sums[:]:
            sums.append(sum_ + number)

        sums.append(number)

    return n in sums


def check_sum_optimized(numbers, n):
    sums1, sums2 = [], []
    numbers1 = numbers[:len(numbers) // 2]
    numbers2 = numbers[len(numbers) // 2:]

    for sums, numbers_ in ((sums1, numbers1), (sums2, numbers2)):
        for number in numbers_:
            for sum_ in sums[:]:
                sums.append(sum_ + number)

            sums.append(number)

    for sum_ in sums1:
        if n - sum_ in sums2:
            return True

    return False


assert check_sum_bruteforce([1, 2, 3, 4, 5, 10], 19)
assert check_sum_optimized([1, 2, 3, 4, 5, 10], 19)

import timeit

print(
    "Bruteforce approach (10000 times):",
    timeit.timeit(
        'check_sum_bruteforce([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 200)',
        number=10000,
        globals=globals()
    )
)

print(
    "Optimized approach by Jonathan (10000 times):",
    timeit.timeit(
        'check_sum_optimized([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 200)',
        number=10000,
        globals=globals()
    )
)

Output (the float numbers are seconds):

Bruteforce approach (10000 times): 1.830944365834205
Optimized approach by Jonathan (10000 times): 0.34162875449254027

Answer 2

The brute force approach requires generating 2^(array_size)-1 subsets to be summed and compared against target N.

The run time can be dramatically improved by simply splitting the problem in two. Store, in sets, all of the possible sums for one half of the array and the other half separately. It can now be determined by checking for every number n in one set if the complementN-n exists in the other set.

This optimization brings the complexity down to approximately: 2^(array_size/2)-1+2^(array_size/2)-1=2^(array_size/2 + 1)-2 Half of the original.

Here is a c++ implementation using this idea.

#include <bits/stdc++.h>
using namespace std; 
bool sum_search(vector<int> myarray, int N) {
        //values for splitting the array in two
        int right=myarray.size()-1,middle=(myarray.size()-1)/2;

        set<int> all_possible_sums1,all_possible_sums2;

        //iterate over the first half of the array
        for(int i=0;i<middle;i++) {
            //buffer set that will hold new possible sums
            set<int> buffer_set;

            //every value currently in the set is used to make new possible sums
            for(set<int>::iterator set_iterator=all_possible_sums1.begin();set_iterator!=all_possible_sums1.end();set_iterator++) 
                buffer_set.insert(myarray[i]+*set_iterator);

            all_possible_sums1.insert(myarray[i]);

            //transfer buffer into the main set
            for(set<int>::iterator set_iterator=buffer_set.begin();set_iterator!=buffer_set.end();set_iterator++) 
                all_possible_sums1.insert(*set_iterator);
        } 

        //iterator over the second half of the array
        for(int i=middle;i<right+1;i++) {
            set<int> buffer_set;    

            for(set<int>::iterator set_iterator=all_possible_sums2.begin();set_iterator!=all_possible_sums2.end();set_iterator++)   
                buffer_set.insert(myarray[i]+*set_iterator);

            all_possible_sums2.insert(myarray[i]);

            for(set<int>::iterator set_iterator=buffer_set.begin();set_iterator!=buffer_set.end();set_iterator++) 
                all_possible_sums2.insert(*set_iterator);
        }

        //for every element in the first set, check if the the second set has the complemenent to make N
        for(set<int>::iterator set_iterator=all_possible_sums1.begin();set_iterator!=all_possible_sums1.end();set_iterator++)  
            if(all_possible_sums2.find(N-*set_iterator)!=all_possible_sums2.end()) 
                return true;                                       
        return false;
}

Answer 3

Ugly and brute force approach:

 a = [1, 2, 3, 4, 5, 10]
 b = []
 a.size.times do |c|
    b << a.combination(c).select{|d| d.reduce(&:+) == 19 }
 end
 puts b.flatten(1).inspect