Total sum from a set (logic)

Question

I have a logic problem for an iOS app but I don't want to solve it using brute-force.

I have a set of integers, the values are not unique:

[3,4,1,7,1,2,5,6,3,4........]

How can I get a subset from it with these 3 conditions:

I can only pick a defined amount of values.
The sum of the picked elements are equal to a value.
The selection must be random, so if there's more than one solution to the value, it will not always return the same.

Thanks in advance!

Have you read that [SO question](http://stackoverflow.com/questions/9656789/find-2-numbers-in-an-unsorted-array-equal-to-a-given-sum)? — Azat, Apr 08 '15 at 10:49
and also http://stackoverflow.com/questions/2070359/finding-three-elements-in-an-array-whose-sum-is-closest-to-an-given-number — Paulw11, Apr 08 '15 at 10:54
Yea, both related question do not fit this one because (1) number of items is unlimited here. (2) None asks for a random choice if multiple solutions exist. — amit, Apr 08 '15 at 10:55
As Amit points out in his answer the problem is NP-Complete. You didn't mention an unlimited number of items in your question though - this means you can't sort the items — Paulw11, Apr 08 '15 at 10:59
The number of items is limited, but the solution needs to be random if there are more than one option — mtet88, Apr 08 '15 at 11:57

amit · Accepted Answer · 2015-04-10T11:12:29.513

This is the subset sum problem, it is a known NP-Complete problem, and thus there is no known efficient (polynomial) solution to it.

However, if you are dealing with only relatively low integers - there is a pseudo polynomial time solution using Dynamic Programming.

The idea is to build a matrix bottom-up that follows the next recursive formulas:

D(x,i) = false   x<0
D(0,i) = true
D(x,0) = false   x != 0
D(x,i) = D(x,i-1) OR D(x-arr[i],i-1)

The idea is to mimic an exhaustive search - at each point you "guess" if the element is chosen or not.

To get the actual subset, you need to trace back your matrix. You iterate from D(SUM,n), (assuming the value is true) - you do the following (after the matrix is already filled up):

if D(x-arr[i-1],i-1) == true:
    add arr[i] to the set
    modify x <- x - arr[i-1]
    modify i <- i-1
else // that means D(x,i-1) must be true
    just modify i <- i-1

To get a random subset at each time, if both D(x-arr[i-1],i-1) == true AND D(x,i-1) == true choose randomly which course of action to take.

Python Code (If you don't know python read it as pseudo-code, it is very easy to follow).

arr = [1,2,4,5]
n = len(arr)
SUM = 6
#pre processing:
D = [[True] * (n+1)]
for x in range(1,SUM+1):
    D.append([False]*(n+1))
#DP solution to populate D:
for x in range(1,SUM+1):
    for i in range(1,n+1):
        D[x][i] = D[x][i-1]
        if x >= arr[i-1]:
            D[x][i] = D[x][i] or D[x-arr[i-1]][i-1]
print D

#get a random solution:

if D[SUM][n] == False:
    print 'no solution'
else:
    sol = []
    x = SUM
    i = n
    while x != 0:
        possibleVals = []
        if D[x][i-1] == True:
            possibleVals.append(x)
        if x >= arr[i-1] and D[x-arr[i-1]][i-1] == True:
            possibleVals.append(x-arr[i-1])
        #by here possibleVals contains 1/2 solutions, depending on how many choices we have.
        #chose randomly one of them
        from random import randint
        r = possibleVals[randint(0,len(possibleVals)-1)]
        #if decided to add element:
        if r != x:
            sol.append(x-r)
        #modify i and x accordingly
        x = r
        i = i-1
    print sol

P.S.

The above give you random choice, but NOT with uniform distribution of the permutations.
To achieve uniform distribution, you need to count the number of possible choices to build each number.
The formulas will be:

D(x,i) = 0 x<0
D(0,i) = 1
D(x,0) = 0   x != 0
D(x,i) = D(x,i-1) + D(x-arr[i],i-1)

And when generating the permutation, you do the same logic, but you decide to add the element i in probability D(x-arr[i],i-1) / D(x,i)

Hi Amit, thank you very much for your help, do you know if there's any way to limit the solution only to a certain amount of values? For example, assuming there will always be an answer, get only a solution with X values — mtet88, Apr 10 '15 at 13:43
@mtet88 yes, add a dimension with number of values used, and modify the recursivr formula to `D(x,i,j) = D(x-arr[i],i-1,j-1) OR D(x,i-1,j)`, and change stop clauses accordingly so only `D(0,i,0) = true`. Similar solution for counting number of subsets. — amit, Apr 10 '15 at 14:13
I'm really really sorry being this annoying, I'm completely lost... With this I can create the new matrix (cube in this case) with this logic: D(x,i,j) = 0 x<0 || j<0 D(0,i,0) = 1 D(x,0,j) = 0 x != 0 && j!=0 D(x,i,j) = D(x-arr[i],i-1,j-1) OR D(x,i-1,j) but what next? the method that actually gets the solution completely changes — mtet88, Apr 10 '15 at 14:55

Total sum from a set (logic)

1 Answers1

Linked