What's wrong with my iterative backtracking algorithm?

Question

So I am working on an iterative backtracking algorithm to solve this task:

Generate all subsequences of length 2n+1, formed only by 0, -1 or 1, such that a₁ = 0, ..., a_2n+1= 0 and |a_i+1 - a_i| = 1 or 2, for any 1 ≤ i ≤ 2n.

This is what I tried:

def is_ok(list, k):
    for i in range(1, k + 1):
        if abs(list[i] - list[i-1]) == 0:
            return False
    if k == len(list)-2:
        if abs(list[k+1]-list[k]) == 0:
            return False
    return True

def back_iter(n):
    list_size = n*2+1
    solution = [-1] * list_size
    solution[0] = 0
    solution[2*n] = 0
    position = 1
    while position >= 1:
        if is_ok(solution, position) and position < 2*n-1:
            if position == 2*n-2:
                print(solution)

            position += 1
            solution[position] = -1
        else:
            while solution[position] == 1:
                solution[position] = -1
                position -= 1
            if position < 1:
                break
            solution[position] += 1

My output for n=2:

[0, -1, 0, -1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, -1, 0]
[0, 1, 0, -1, 0]

Expected output for n=2:

[0, -1, 0, -1, 0]
[0, -1, 0, 1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, 1, 0]
[0, 1, 0, -1, 0]
[0, 1, 0, 1, 0]

Answer 1

everything is correct in your code, but you are printing at wrong place

def is_ok(arr, i):
    return abs(arr[i]-arr[i-1]) in (1,2)

def back_iter(n):
    list_size = n*2+1
    solution = [-1] * list_size
    solution[0] = 0
    solution[2*n] = 0
    position = 1
    while position >= 1:
        
        if is_ok(solution, position) and position < 2*n-1:
            position += 1
            solution[position] = -1
          
        else:
            if is_ok(solution, position) and position == (2*n-1) and solution[position]:
                print(solution)
            while solution[position] == 1:
                solution[position] = -1
                position -= 1
            
            if position < 1:
                break
            solution[position] += 1
            

back_iter(2)

# output 
[0, -1, 0, -1, 0]
[0, -1, 0, 1, 0]
[0, -1, 1, -1, 0]
[0, 1, -1, 1, 0]
[0, 1, 0, -1, 0]
[0, 1, 0, 1, 0]