Disclaimer: I'm honestly not sure whether this question is best placed at Puzzling, Maths, or Programming SE, but I'm interested in the best solution, and I'm sure mods will shift the question around, if inappropriate... It is definitely something I have been puzzling over for a while now...
(Maybe I'm just having a dumb day and need some fresher brain...)

You have a sack of N identical Lego bricks, which can be built into a row of M Lego-stacks of arbitrary height.

enter image description here

Obviously, one extreme is a single stack of N bricks, while the other is a row of N single bricks.

enter image description here

Two different in-between possibilities would for example be:

enter image description here

You are interested in a complete, duplicate free list of all possible solutions. What is the most efficient algorithm which outputs all possible rows that exist for any given N? The order in which the individual possibilities are output is not important.

For clarification:

  • All bricks are identical
  • Stack positions in the row are of importance, that's why the above example shows two different possibilities
  • All stacks are always next to each other, i.e. a 'zero-sized-stack' on either side or in between would not constitute a solution.

Using numbers to denote stack-height and position to denote stack-position, the correct output of the algorithm for N = 4 bricks would be the following eight results (in any order):

[ 1 1 1 1 ]
[ 2 1 1 ]
[ 1 2 1 ]
[ 1 1 2 ]
[ 3 1 ]
[ 2 2 ]
[ 1 3 ]
[ 4 ]

A valid answer provides the algorithm description in pseudo-code (or real code) which gives this output for any given input N. The most efficient (correct) code gets accepted.

  • $\begingroup$ Clarification: By efficient I mean computationally efficient and not shortest possible source code. $\endgroup$
    – BmyGuest
    Apr 5, 2018 at 17:28
  • $\begingroup$ Not exactly what you are looking for, but you could use the concept of a partition $\endgroup$ Apr 5, 2018 at 20:45
  • $\begingroup$ Use the Mathematica function "IntegerPartitions" $\endgroup$
    – John
    Apr 5, 2018 at 21:06
  • 1
    $\begingroup$ @Justabrowsingguest These are not partitions, they're compositions. $\endgroup$
    – ffao
    Apr 5, 2018 at 21:12
  • 2
    $\begingroup$ There's very little to optimize if you want to actually output each possibility; counting possibilities has a lot more room for optimization beyond brute force. $\endgroup$ Apr 5, 2018 at 21:41

3 Answers 3


Let $n$ be the number of bricks. Iterate from $i = 0$ to $2^{n-1}$ and write it as binary. Start your first tower with 1 brick, and as long as you encounter 0s, you add one layer. If you encounter a 1, start a new tower. Example for $n = 4$:

000 -> 4
001 -> 3 1
010 -> 2 2
011 -> 2 1 1
100 -> 1 3
101 -> 1 2 1
110 -> 1 1 2
111 -> 1 1 1 1

Here is a visualization of how an 8-bit binary number 00010110 corresponds 1-1 with a composition of $n=9$ bricks:

enter image description here

  • 1
    $\begingroup$ This is very neat. I'll need to verify and implement (not today anymore though), but I like what I'm seeing. Do you know a nice "programmer's" trick to perform the binary to "list" transformation efficiently as well? C++ code or similar. I'm just naivly going for a real looped check, but my gut-instincts tells me, there might be something better out there... $\endgroup$
    – BmyGuest
    Apr 5, 2018 at 18:37
  • 1
    $\begingroup$ @BmyGuest this can get as complicated as you want it to be (search for "count trailing zeros"), but there's not really a "simple" way, unless you count using builtin functions (in gcc, this would be __builtin_ctz). $\endgroup$
    – ffao
    Apr 5, 2018 at 19:10
  • 2
    $\begingroup$ Here is a simple way to see why this works. Suppose you stick the pieces together in one pile, but lay it on its side. At any seam between two bricks you can split it, or keep it as is, and in doing so you can split it in any size parts as you want. Once you are done, you tilt the parts vertical without changing their order to get a pile arrangement. Any valid arrangement is possible, and each can be created in only one way via this method. The number of ways of doing it is therefore equal to the number of choices for breaking at the seams - a factor of $2$ per seam, i.e. $2^{N-1}$ in total. $\endgroup$ Apr 6, 2018 at 13:46
  • $\begingroup$ @JaapScherphuis Nice illustration. $\endgroup$
    – BmyGuest
    Apr 6, 2018 at 14:01
  • $\begingroup$ @JaapScherphuis thanks for the illustration and the edit on my visual interpretation of it. $\endgroup$
    – Glorfindel
    Apr 7, 2018 at 8:02

A simple $O(2^n)$ algorithm written in Python (@Glorfindel's is $O(n\cdot2^n)$):

def ordered_compositions(n):
  Yield all ordered compositions of n.
  if n == 1:
    yield [1]
    for composition in ordered_compositions(n - 1):
      composition[-1] += 1 # add 1
      yield composition
      composition[-1] -= 1 # remove the added 1
      composition.append(1) # other way to add 1
      yield composition
      composition.pop() # remove added 1

for composition in ordered_compositions(4):

Note that this mutates compositions (towers) after yielding them (this is why $O(2^n)$ is possible), so if you want to make a list from it, you'll have to copy each composition.

This algorithm can be found by noting that each composition of $n$ is a composition of $n-1$, with a $1$ added to the end, or with $1$ added to the last number.

For example,

the compositions of 2 are:

[1, 1]

and the compositions of 3 are:

[3]       ([2 + 1])
[2, 1]    ([2] + [1])
[1, 2]    ([1, 1 + 1])
[1, 1, 1] ([1, 1] + [1])

This algorithm could also be implemented by keeping a bool array of length $n-1$ (representing appending to the list, or adding to the last element), and a int vector (the composition). The bool array would start all false, and the vector containing $n$.

Each step would go something like this (in psuedocode), until the bool array is all ones (after $2^{n-1}$ steps):

count = 0
while (bools[count])
  pop from vector // remove the 1 brick we added when bools[count] was set
  bools[count] = false
  count += 1

pop from vector
append popped + count // combine the removed bricks to one tower

process partition

bools[count]  = true // ends a tower 1 brick earlier
pop from vector
append popped - 1 // remove the 1 brick
append 1          // add it to a new tower

This would produce results like this:

000 -> 4
100 -> 31
010 -> 22
110 -> 211
001 -> 13
101 -> 121
011 -> 112
111 -> 1111

These results are the same as Glorfindel's since the algorithms are actually the same (see annotations in the code). The only difference is that mine changes each result into the next, instead of rebuilding it each time.

  • 1
    $\begingroup$ Any practical use of this list is probably going to be O(n * 2^n) anyway, but this is an interesting optimization so you get +1 from me $\endgroup$
    – ffao
    Apr 5, 2018 at 19:11
  • $\begingroup$ Even the print loop in the answer is already O(n * 2^n). $\endgroup$ Apr 5, 2018 at 21:40
  • $\begingroup$ @user2357112 True, but the generation isn't. $\endgroup$ Apr 5, 2018 at 21:48

A simple backtracking approach. $\mathcal{O}(n 2^n)$. Definitely not faster than the accepted answer. Just add a more canonical approach to this type of problems.

#include <iostream>
#include <vector>

std::vector<int> solution;
std::ostream& operator<<(std::ostream& os, const std::vector<int>& v)
    os << "[";
        auto iter = std::begin(v);
        os << *iter;
            os << ", " << *iter;
    os << "]";
    return os;
void f(int n)
    if(n == 0)
        std::cout << solution << std::endl;
        // Append new item to list. Equivalent to a 1-bit
        solution.pop_back(); // Backtrack
        // Increment last item in the list. Equivalent to a 0-bit.
        solution.back()--; // Backtrack
void solve(int N)

int main() {
    int N = 4;
    return 0;

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.