Find vector elements that sum up to specific number

16 views (last 30 days)
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.

Accepted Answer

Jos (10584)
Jos (10584) on 13 Feb 2013
NCHOOSECRIT is now available, so:
vect = [2 5 7 10]
num = 17
answer = nchoosecrit(vect, @(x) sum(x)==num)

More Answers (3)

Carlos
Carlos on 13 Feb 2013
Edited: Carlos on 14 Feb 2013
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...

Jos (10584)
Jos (10584) on 13 Feb 2013
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:
  1 Comment
Jos (10584)
Jos (10584) on 13 Feb 2013
FYI, I just uploaded a function NCHOOSECRIT to the File Exchange that might be useful to you.

Sign in to comment.


ToLos Mil
ToLos Mil on 15 Feb 2013
Thank you all for your time and great solutions.
An issue remains... what if the original vector (vect) contains many elements?
  2 Comments
ChristianW
ChristianW on 15 Feb 2013
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)
Jos (10584) on 15 Feb 2013
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.

Sign in to comment.

Categories

Find more on Numeric Types in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!