All possible combinations, such that the sum of all numbers is a fixed number

Question

I need to find all possible combinations of the numbers 1: 8, so that the sum of all the elements is 8. The combinations should be arranged in ascending order.

For instance,

1 7

2 2 4

1 3 5

1 2 2 3

1 1 1 1 1 1 1 1

The number can be repeated. But the combination should not ... that is, 1 2 2 3 and 2 1 2 3 I need a solution in ascending order. Thus, there will be only one possibility of each combination

I tried several codes on the Internet suggested on Find vector elements that add up to a specific number in MATLAB

   VEC = [1:8];
      NUM = 8;
      n = length(VEC);
      finans = zeros(2^n-1,NUM);
      for i = 1:(2^n - 1)
        ndx = dec2bin(i,n) == '1';
        if sum(VEC(ndx)) == NUM
        l = length(VEC(ndx));
        VEC(ndx)
        end
      end

but they do not include the ability to repeat numbers.

Answer 1

: !

! cartprod.m .

% Create all permutations
p(1:8) = {0:8};
M = fliplr( cartprod( p{:} ) );

% Check sums
r = sum( M, 2 ) == 8;
M = M(sum( M, 2 ) == 8,:);   % Solution here

, , , . , Matlab 3,5 , .

---

Answer 2

, ( ) , ( 0.00399705213 ).

EDIT: stretchmat.m, , . Kinda, repmat, (. ). !

script.

% Define funciton to prepend a cell x with a variable i
cellprepend = @(x,i) {[i x]};

% Execute and time function
tic;
a = allcomb(cellprepend,1,8);   % Solution in a
toc;

allcomb.m

function a = allcomb( cellprepend, m, n )
    % Add entire block as a combination
    a{1} = n;

    % Exit recursion if block size 1
    if n == 1
        return;
    end

    % Recurse cutting blocks at different segments
    for i = m:n/2
        b = allcomb(cellprepend,i,n-i);
        a = [a cellfun( cellprepend, b, num2cell( stretchmat( i, b ) ) )];
    end
end

, , , 8, . , , 2 . , , Merge Sort. Allcomb call (n) .

, 1: n-1. . , , .

, , . , , , , . ? script.m.

EDIT 2/3

• @Simon QA

Answer 3

. nmultichoosek.

v = 1 : 8;
combs = cell(length(v),0);
for i = v
    combs{i} = nmultichoosek(v,i);
end

, combs , . , i-th combs{4} .

. , cellfun

sums = cellfun(@(x)sum(x,2),combs,'UniformOutput',false);

sums . sums{4} combs{4}.

- .

fixed_sum = 10;
indices = cellfun(@(x)x==fixed_sum,sums,'UniformOutput',false);

indices , , . , indices{4}(1) , 4 fixed_sum.

, , .

valid_combs = cell(length(v),0);
for i = v
    idx = indices{i};
    c = combs{i};
    valid_combs{i} = sortrows(c(idx,:));
end

valid_combs- this is a cell similar to combs, but only with combinations that are summed to the desired value and sorted by the number of numbers used: it valid_combs{1}has all valid combinations with 1 number, valid_combs{2}with two numbers, etc. In addition, thanks sortrows, combinations with the same number of numbers are also sorted. For example, if fixed_sum = 10, that valid_combs{8}is,

 1     1     1     1     1     1     1     3
 1     1     1     1     1     1     2     2

This code is pretty efficient, on my oldest laptop I can run it in 0.016947 seconds.