Q:

Coming with a procedure to generate an array with special properties

I have an array of size n. Each element can hold any integer as long as the following properties holds:
1) All elements are non-negative
2) sum(array[0,i+1])<i for 0<=i<n 
3) sum(array)=n-1

Let's call such an array a bucket.
I need to come up with a procedure that will generate the next bucket.
We can assume the first bucket is {0,0,0...n-1}
Example: For n=5, some possible combinations are
[0 0 0 0 4]    
[0 0 0 1 3]    
[0 0 0 2 2]    
[0 0 0 3 1]    
[0 0 1 2 1]    
[0 0 2 1 1]    
[0 1 1 1 1]    
[0 1 0 0 3]    
[0 1 1 0 2]

I'm having trouble coming up with a procedure that hits all the possible combinations. Any hints/tips? (Note I want to generate the next bucket. I'm not looking to print out all possible buckets at once)

A:

You can use a simple backtracking procedure. The idea is to keep track of the current sum and the current index i.  This would allow you to express the required constrains.
n = 5
a = [0] * n

def backtrack(i, sum):
    if i > 0 and sum > i-1:
        return
    if i == n:
        if sum == n-1:
            print(a)
        return
    for e in range(n-sum):
        a[i] = e
        backtrack(i + 1, sum+e)

backtrack(0, 0)

test run

