Function that return set (vector) of integers that are sum of other integer

Question

I am looking for a Matlab function, that help me to set a vector of integers, that multiplied by other known vector will be a sum of the other known integer.

For example:

V = [1, 2, 3, 4]
X = 10
results =
[10, 0, 0, 0] 
[8, 1, 0, 0]
.....
[0, 2, 0, 2]
etc.

I am trying to solve a problem similar to discrete knapsack problem.

Answer 1

You could always use brute force (there may be more efficient approaches, though):

%// Data
V = [1 2 3 4];
X = 10;

%// Generate all combinations of n integers from 0 to X
%// (same approach as in http://stackoverflow.com/q/21895335/2586922 )
n = numel(V);
c = cell(1,n);
[c{:}] = ndgrid(0:X);
c = cat(n+1,c{:});
c = reshape(c,[],n);

%// Test which combinations are valid, and keep only those
s = sum(bsxfun(@times, c, V),2);
result = c(s==X,:);

In your example, there are 23 valid combinations:

result = 
    10     0     0     0
     8     1     0     0
     6     2     0     0
     4     3     0     0
     2     4     0     0
     0     5     0     0
     7     0     1     0
     5     1     1     0
     3     2     1     0
     1     3     1     0
     4     0     2     0
     2     1     2     0
     0     2     2     0
     1     0     3     0
     6     0     0     1
     4     1     0     1
     2     2     0     1
     0     3     0     1
     3     0     1     1
     1     1     1     1
     0     0     2     1
     2     0     0     2
     0     1     0     2