Efficiently generate all vector partitions

Question

A vector partition is splitting a vector up a series of vectors such that their sum is the original. Here are a couple partitions:

[3, 1, 2] = [3, 1, 2]
[3, 1, 2] = [0, 0, 1] + [0, 0, 1] + [0, 1, 0] + [1, 0, 0] + [2, 0, 0]
[3, 1, 2] = [1, 1, 2] + [2, 0, 0]

Here vector addition is done element-wise. A valid partition does not contain any vectors with negative integers, or the all-zero vector.

Now the challenge is to write a program or function that generates all possible vector partitions given a target vector. This may sound relatively easy...

...but there is a twist. If the input vector has size L, and the biggest partition it generates has M elements, you may not use more than O(L*M) memory.

You may assume that an integer uses O(1) memory. This means that you must output the partitions as you generate them. On top of that, you must only output each partition exactly once. For example, these are the same partition:

[3, 1, 2] = [3, 0, 2] + [0, 1, 0]
[3, 1, 2] = [0, 1, 0] + [3, 0, 2]

If you were to output both your answer is invalid.

---

All partitions for [3, 2]:

[3, 2]
[0, 1] + [3, 1]
[0, 1] + [0, 1] + [3, 0]
[0, 1] + [0, 1] + [1, 0] + [2, 0]
[0, 1] + [0, 1] + [1, 0] + [1, 0] + [1, 0]
[0, 1] + [1, 0] + [2, 1]
[0, 1] + [1, 0] + [1, 0] + [1, 1]
[0, 1] + [1, 1] + [2, 0]
[0, 2] + [3, 0]
[0, 2] + [1, 0] + [2, 0]
[0, 2] + [1, 0] + [1, 0] + [1, 0]
[1, 0] + [2, 2]
[1, 0] + [1, 0] + [1, 2]
[1, 0] + [1, 1] + [1, 1]
[1, 1] + [2, 1]
[1, 2] + [2, 0]

To test your answer, run it on [3, 2, 5, 2]. It should generate 17939 partitions, all of which sum to [3, 2, 5, 2], and that are all unique (you can test for uniqueness by first sorting each partition lexicographically).

---

Shortest code in bytes wins.

Answer 1

Python 2, 289 bytes

Simple brute force algorithm. Treats entire list as a number in base max(input)+1 (b), and checks each "number" in the range [0, b**(L*M)) to see if it:

1. Sums to the correct amount
2. Is in alphabetical order (ensures uniqueness)

If the list matches these criteria, the program outputs it with all the all-zero vectors stripped.

Memory usage

The largest data structure I use in this program is a doubly-nested list, an list length M containing liss length L to give O(L*M) memory.

For my other data structures, I have 3 global ints O(3), 1 list length L (O(L)), 1 array length M (O(M)), and a copy of the largest array when outputting (O(L*M)).

In total, this gives me a memory usage of O(2*L*M + L + M + 3) which simplifies to O(L*M), fufilling the criteria.

Time complexity

Being a brute force algorithm, this algorithm is extremely slow. For the while loop to quit, the final int in the array needs to be b-1. The loop needs to run b**(L*M) times before that happens.

In addition, each time the list runs, it needs to check both conditions, and print the list in a worst case, using L*M+L+M iterations. This simplifies to give an overall O(L*M * b**(L*M)). I tried to test my program on [3, 2, 5, 2], but gave up after 45 minutes.

Golfed program

v=input()
L=len(v)
M=sum(v)
b=max(v)
R=range
t=[L*[0]for i in R(M)]
def A(l,i):
 if i<L*M-1and~-b<l[i/L][i%L]:A(l,i+1)
 l[i/L][i%L]=-~l[i/L][i%L]%-~b
while t[-1][-1]<b:
 if v==[sum(q[i]for q in t)for i in R(L)]and all(`t[i]`>=`t[i+1]`for i in R(M-1)):print[x for x in t if[0]*L!=x]
 A(t,0)

I might be able to golf this a bit more, especially the increment part. Ungolfed code coming.