Generate all possible combinations summing up to a given number

I could do it using nested loops manually. What I wanted is, it should automatically generate using the given value n.

Depending on n it should generate all possible combinations in which it can be summed up to n where the numbers must be filled only in n positions.

For example this program

clc
clear
n=3;
t=1;
for hh=0:n
    for ii=0:n
        for jj=0:n
            aa=[n-hh,n-ii,n-jj];
            if sum(aa(:))==n
                aa1(t,:)=aa;
                t=t+1;
            end
        end
    end
end
aa1

This generates

aa1 =

     3     0     0
     2     1     0
     2     0     1
     1     2     0
     1     1     1
     1     0     2
     0     3     0
     0     2     1
     0     1     2
     0     0     3

But I will have to increase the loops manually if I change n. Can the numbers be generated automatically depending on n. For my use n would be usually greater than 3. Note that the numbers always sum up to n in each row.

[Nishant Pathak]

For example for n=2, it should give

0 2

2 0

1 1

Answer 1

[Paul]

n = 3;
[C{1:n}] = ndgrid(0:n);
C = cell2mat(cellfun(@(x)(reshape(x,[],1)),C,'UniformOutput',false));
C(sum(C,2) == n,:)

ans = 10×3

3 0 0 2 1 0 1 2 0 0 3 0 2 0 1 1 1 1 0 2 1 1 0 2 0 1 2 0 0 3

[Nishant Pathak]

Thank you so much. BTW it is giving error if I don't clear clear the variables

Unable to perform assignment
because brace indexing is not
supported for variables of
this type.

Error in untitled (line 4)
[C{1:n}] = ndgrid(0:n);

[Paul]

Yes, on this line

[C{1:n}] = ndgrid(0:n);

C has to be either an n-element cell array or a not-yet-defined variable. So you can always do something like:

n = 2;
C = cell(1,n);  % pre-allocate C
[C{1:n}] = ndgrid(0:n);
C = cell2mat(cellfun(@(x)(reshape(x,[],1)),C,'UniformOutput',false));
C(sum(C,2) == n,:)

ans = 3×2

2 0 1 1 0 2

[Nishant Pathak]

Thanks a lot for the help.

Answer 2

[John D'Errico]

These are commonly known to mathematicians as integer partitions, thus the ways we can write an integer as a sum of smaller integers. But be careful, as the number of such ways quickly becomes huge for only reasonably small N. I posted somewhere a code that computes the actual number of ways you can do this. But Wolfram Alpha does it too. (There are something like 4 trillion distinct ways to write 200 as a sum of positive integers.)

I also posted the function partitions on the file exchange, that uses a recursive scheme to compute all integer partitions of any number. (Too large and you will be sorry of course.)

partitions(3)
ans =
3     0     0
1     1     0
0     0     1

Each row is one such possibe partition. So the first row tells us that 3 = 1 + 1 + 1. In the last row, we only need one 3 to sum up to 3.

partitions(10)
ans =
10     0     0     0     0     0     0     0     0     0
8     1     0     0     0     0     0     0     0     0
6     2     0     0     0     0     0     0     0     0
4     3     0     0     0     0     0     0     0     0
2     4     0     0     0     0     0     0     0     0
0     5     0     0     0     0     0     0     0     0
7     0     1     0     0     0     0     0     0     0
5     1     1     0     0     0     0     0     0     0
3     2     1     0     0     0     0     0     0     0
1     3     1     0     0     0     0     0     0     0
4     0     2     0     0     0     0     0     0     0
2     1     2     0     0     0     0     0     0     0
0     2     2     0     0     0     0     0     0     0
1     0     3     0     0     0     0     0     0     0
6     0     0     1     0     0     0     0     0     0
4     1     0     1     0     0     0     0     0     0
2     2     0     1     0     0     0     0     0     0
0     3     0     1     0     0     0     0     0     0
3     0     1     1     0     0     0     0     0     0
1     1     1     1     0     0     0     0     0     0
0     0     2     1     0     0     0     0     0     0
2     0     0     2     0     0     0     0     0     0
0     1     0     2     0     0     0     0     0     0
5     0     0     0     1     0     0     0     0     0
3     1     0     0     1     0     0     0     0     0
1     2     0     0     1     0     0     0     0     0
2     0     1     0     1     0     0     0     0     0
0     1     1     0     1     0     0     0     0     0
1     0     0     1     1     0     0     0     0     0
0     0     0     0     2     0     0     0     0     0
4     0     0     0     0     1     0     0     0     0
2     1     0     0     0     1     0     0     0     0
0     2     0     0     0     1     0     0     0     0
1     0     1     0     0     1     0     0     0     0
0     0     0     1     0     1     0     0     0     0
3     0     0     0     0     0     1     0     0     0
1     1     0     0     0     0     1     0     0     0
0     0     1     0     0     0     1     0     0     0
2     0     0     0     0     0     0     1     0     0
0     1     0     0     0     0     0     1     0     0
1     0     0     0     0     0     0     0     1     0
0     0     0     0     0     0     0     0     0     1

You can find partitions on the file exchange. Partitions has many options beyond the basic of course.

https://www.mathworks.com/matlabcentral/fileexchange/12009-partitions-of-an-integer?s_tid=srchtitle

[Steven Lord]

FYI sequence A000041 in the On-Line Encyclopedia of Integer Sequences is the number of partitions of n. Note that this treats two partitions with the same numbers in a different order the same, so the two partitions of 2 are {2, 0} (or just plain {2}) and {1, 1}. {0, 2} is not treated as another partition.

Answer 3

[Bruno Luong]

You can use this file exchange

https://www.mathworks.com/matlabcentral/fileexchange/17818-all-permutations-of-integers-with-sum-criteria

n = 3;
allVL1(n,n,'==') % first parameter 3 columns, second parameter each row sum to 3

ans =

0     0     3
0     1     2
0     2     1
0     3     0
1     0     2
1     1     1
1     2     0
2     0     1
2     1     0
3     0     0

[Bruno Luong]

The number of solutions for given n can be obtained

>> n=10;
>> allVL1(n,n,'==',NaN)

ans =

92378

It is in fact equal to

>> nchoosek(2*n-1,n)

ans =

92378