Combinations of stepwise increasing integers Working on something in probability theory, I stumbled across another combinatorical exercise. These are always fun to solve, searching for intelligent approaches. Of course, one can use brute force for the following task, but this challenge is restricted complexity, so this is not allowed.

Task

Given an integer Input \$n &gt; 1\$, print all integer vectors of length \$n\$, respecting following conditions:


\$v_1 = 1\$
\$v_{i+1} - v_i \in \{0,1\}\$
\$v_n \neq n\$


example:

Input: 

n=4

Output:

[1 1 1 1]

[1 1 1 2]

[1 1 2 2]

[1 1 2 3]

[1 2 2 2]

[1 2 2 3]

[1 2 3 3]


Additionally, time complexity of your solution must be \$O(2^n)\$. Note that generating all vectors and then filtering would be \$O(n^n)\$, which is not acceptable. A direct construction, not generating any false vector or duplicate vector at all, seems to be a bit more of a challenge.

Having said that, shortest code in bytes, respecting the above condition, wins.
Ruby, 65 55 bytes

-&gt;n{(0..2**~-n-2).map{|x|w=1;(1..n).map{|d|w+=x[n-d]}}}

Try it online!
How:
Partial sum of bits (starting with 1) of all numbers up to 2n-1-2
For example: if the number is 111010011 it becomes:
  1 1 1 0 1 0 0 1 1
  | | |   |     | |
  v v v   v     v v
 +1+1+1  +1    +1+1
  -----------------
1 2 3 4 4 5 5 5 6 7
|
Initialized to 1