CODEWITHSUNDEEP
matlabcombinatorics
ToLos Mil
ToLos Mil

Reputation: 73

Find vector elements that sum up to specific number in MATLAB

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.

Upvotes: 2

Views: 3072

Answers (3)

shoelzer
shoelzer

Reputation: 10708

Here's another way to do it without any toolboxes or third party functions. It steps through all possible combinations of values in VEC and tests if the sum equals NUM.

VEC = [2 5 7 10]
NUM = 17;
n = length(VEC);
for i = 1:(2^n - 1)
    ndx = dec2bin(i,n) == '1';
    if sum(VEC(ndx)) == NUM
        VEC(ndx)
    end
end

ans =
     7    10
ans =
     2     5    10

This is similar to natan's answer, but without using conbntns.

Upvotes: 3

Shai
Shai

Reputation: 114786

If I'm not mistaken this problem is NP-hard.
But an interesting approach might be using bintprog:

n = numel( VEC );
x0 = zeros( 1, n ); % one possible init guess
x = bintprog( zeros( n, 1 ), ...  % objective function meaningless, we look for feasibility
              [], [], ... % no inequality constraints
              VEC(:)', NUM, ... %' we want the sum of selected elements to equal NUM
              x0 ); % changing init x0 might result with different solutions
find( x )

the binary vector x (the solution of the optimization in bintprog) selects the relevant elements that sum to NUM

Upvotes: 2

bla
bla

Reputation: 26069

Here is a way to solve this using conbntns, a function from the Mapping Toolbox that retrieves all possible combinations of set of values (if you don't have this toolbox, you can use combinator from the FEX). So, for vector A, for example, we'll find all possible combination of a given length (1 to the length of A) then sum them and see which is equal to NUM=17:

NUM=17;
A=[2 5 7 10];
for ii=1:numel(A)
    B=combntns(A,ii);
    C=sum(B,2);
    D=find(C==NUM);
    if ~isempty(D)
        B(D,:)
    end
end

ans =
     7    10
ans =
     2     5    10

Of course you can store B(D,:) output into a cell array or whatever for future use...

Upvotes: 3

Related Questions