How to find all the combinations of a vector elements whose sum is equal to a given number

Hi all,

I' ve got this vector made of 24 elements:

P = [250 500 500 1250 2500 5000 5000 15000 15000 15000 15000 8166 8926 9796 10800 11967 13333 14948 16875 16875 19200 22041 22041 25562 ]

and I've got a target value "n" to reach by combining a certain number of elements of P and adding them together:

n=3000 (it changes all the times because it's an input given by the user)

Every single element of the vector has to be taken just one time in the sum.

Do you have any ideas of how I can do it? Thanks.

Answer 1

[Stephen23]

A simple recursive nested function, with short-circuiting for combinations whose sums are greater than N (this makes the whole thing viable for small values of N and give results as quickly as possible):

function C = temp4(N)
P = [250,500,500,1250,2500,5000,5000,15000,15000,15000,15000 8166,8926,9796,10800 11967,13333,14948,16875,16875,19200,22041,22041,25562];
C = {};
for ii = 1:numel(P)
    nestfun(P(ii),P(ii+1:end))
end
function nestfun(t,V)
if sum(t)<N
    for jj = 1:numel(V)
        nestfun([t,V(jj)],V(jj+1:end))
    end
elseif sum(t)==N
    C{end+1} = t;
end
end
end

Tested (the repeated vectors are due to the repeated values in P):

>> temp4(3000)
ans = {
[500   2500]
[500   2500]}
>> temp4(30000) % a much more interesting example
ans = {
[250     500     500    1250    2500    5000    5000   15000]
[250     500     500    1250    2500    5000    5000   15000]
[250     500     500    1250    2500    5000    5000   15000]
[250     500     500    1250    2500    5000    5000   15000]
[15000   15000]
[15000   15000]
[15000   15000]
[15000   15000]
[15000   15000]
[15000   15000]
[10800   19200]}

Note that if N is large then you can expect to be waiting for some time... e.g. given all 620,448,401,733,239,000,000,000 combinations at a rate of 1 million checks per second, you would have to wait around

>> yrs = 620448401733239000000000/1e6/60/60/24/365 % years
yrs = 19674289755.62021
>> num2words(yrs,'sigfig',1,'type','money','unit','Year|')
ans = twenty billion years

[Valentina Mazzoni]

Thank you very much, you've made my day!!!

[Valentina Mazzoni]

Now the situation is getting harder:

sometimes it's impossible to find exactly "N" so, istead of finding no solution, I'd like to find the closest value to N.

Is there a way to do it?

Thanks.

[Stephen23]

@Valentina Mazzoni: you can use the same recursive function, just instead of testing for equality you could test if the absolute difference between the values is less than some tolerance value that you select. You might also want to increase the short-circuiting limit, e.g.:

if abs(sum(t)-N)<tol % replace == with abs difference compared against tolerance.
    C{end+1} = t;
elseif sum(t)<(N+tol) % adjust short-circuit limit.
    for jj = 1:numel(V)
        nestfun([t,V(jj)],V(jj+1:end))
    end
end

The current code will stop searching a particular set with the first match: if you want to continue searching that set for other possible matches then split the if-elseif into two separate if statements.

[Valentina Mazzoni]

Thank you very much Stephen, if seems to work fine with the vector P adding a tolerance value. I'll do some more tests tomorrow with the whole code and I'll let you know.

[Valentina Mazzoni]

Hi Stephen, I've done some tests and unfortunally I still have some problems:

1_even if it's possible to reach the exact target value N with a certain combination of values of P, by adding a tolerance I "lose" this chance.

Is there a way to keep the exact combination and to use the tolerance just in case an exact combination doesn't exist?

2_if I have a vector with some zeros, is there a way to take in account only the positive values? I've noticed that they give me problems. e.g.

P = [1000, 2000, 2000, 5000, 10000, 20000, 20000, 60000, 60000, 60000, 60000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0];

Thank you very much.

[Stephen23]

1- "Is there a way to keep the exact combination and to use the tolerance just in case an exact combination doesn't exist?"

Perhaps start with something like this (pseudocode):

if isequal
    ...
elseif is within tolerance
    ...
elseif less than N+tol
    call recursive function
end

Of course this does not prevent the tolerance-comparison matching and also matching the exact match, and so the function returns both of them. So you will need to think about how you can prevent this, e.g.:

1. you might be able to perform a check to see if any future combination (added to the current set) will be an exact match. Most likely this would reduce efficiency.
2. you could store another variable which somehow keeps track of the current set and lets you remove partial matches in the event of a later exact match.

The latter approach might be easier.

As I mentioned in my earlier comment, you will also get a different behavior if you separate this single if-elseif statement into two or three separate if statements: you need to understand and decide based on whichever suits your algorithm logic.

2.- remove the zeros at the start of the parent function, e.g.:

P = [... original data...]
P = nonzeros(P);

[Valentina Mazzoni]

Thank you very much Stephen, you're always very kind. I'll do some tests to find out the best solution for my code.

[Rami Matar]

Hi Stephen,

is there anyway this would work but where we're able to use an element in the P vector more than once? for example lets say my P vector is 1:1:5. I need all combinations of the elements in this vector that sum up to 5 for example. I need [1 1 3] to be a possibility. Thank you in advance.

[Bruno Luong]

I guess you can replace P with Pr like this

>> P=1:5

P =

     1     2     3     4     5

>> s=5

s =

     5

>> Pr=repelem(P,floor(s./P))

Pr =

     1     1     1     1     1     2     2     3     4     5

Then use Stephen's algorithm on Pr.

[Rami Matar]

Thank you Bruno this is just what i needed!