Find vector elements that sum up to specific number

Let us consider that we have a vector VEC.

Is ther a way to find which vector elements can be grouped so as they sum up to a given number NUM in MATLAB?

For example if VEC = [2 5 7 10] and NUM = 17

The requested algorithm should provide the answer that subvectors [2 5 10] and [7 10] sum up to given NUM.

Answer 1

[Jos (10584)]

NCHOOSECRIT is now available, so:

vect = [2 5 7 10]
num = 17
answer = nchoosecrit(vect, @(x) sum(x)==num)

See: http://www.mathworks.com/matlabcentral/fileexchange/40301

Answer 2

[Carlos]

I don´t know any specific Matlab command to adress your problem, however you can write an M-file to solve your problem.

A possible approach to solve your problem is to start checking all the possible combinations of two numbers within your vector. Your algorithm should start checking 2+5=17? no , so continue, 2+7=17? no, 2+10=17?,no 7+10=17?, yes, so I store 7 and 10 in a [2,1] vector(now you should continue checking the rest of the possible combinations of 2 numbers). Then you should do the same with all the possible combinations of 3 different elements, and so on...

Answer 3

[Jos (10584)]

For a small number of elements in vect, you can try this vectorized approach:

vect = [2 5 7 10] 
num = 17

V = nchoose(vect) ;
answer = V(cellfun(@sum,V) == num)

The function NCHOOSE can be found here:

http://www.mathworks.com/matlabcentral/fileexchange/20011

[Jos (10584)]

FYI, I just uploaded a function NCHOOSECRIT to the File Exchange that might be useful to you.

Answer 4

[ToLos Mil]

Thank you all for your time and great solutions.

An issue remains... what if the original vector (vect) contains many elements?

[ChristianW]

You can save maybe 10-20% calculation time with vectorising Pedro's inner for-loop. But the main problem is the fast growing (n choose k). Depending on your memory, its getting hard to calculate it for length(vect) > ~30.

for n = 1:1000
    C(n) = nchoosek(n,round(n/2)); %#ok<*SAGROW>
end
plot(1:n,C); set(gca,'yscale','log')
syms n; L = latex([n;n/2]);
yl = ylabel(['$' L '$'],'interpreter','latex','fontsize',13); xlabel('n')

[Jos (10584)]

For a vector of length N, there are 2^N-1 possible subsets/subvectors. Checking them all will take some time. It depends on the problem and the elements to see whether you can discard certain subsets beforehand, e.g., by removing some elements before you loop over all subsets.