Editing 1357 - Plus Minus

==Cerința==
Fie n un număr natural.
Să se determine toate posibilitățile de alegere a semnelor + și - pentru care
n = (+|-) 12  + (+|-) 22 + ... + (+|-) n2

==Date de intrare==
Fișierul de intrare plusminus.in conține pe prima linie numărul n.

==Date de ieșire==
Fișierul de ieșire plusminus.out va conține pe fiecare linie o succesiune de n semne + sau - , separate prin câte un spațiu, reprezentând câte o soluție a problemei. Dacă nu există soluție, atunci fișierul de ieșire va conține pe prima linie mesajul IMPOSIBIL.

==Restricții și precizări==
1 ≤ n ≤ 23
șirurile se vor afișa în ordine lexicografica; caracterul - este considerat mai mic decăt caracterul +
==Exemplu==:
plusminus.in

9
plusminus.out

- - + - + - + + - 
+ - - + - - + - +
+ + - - + + - - +
+ + + + - + - - +
==Explicație==
Sunt 4 posibilități:
1) 9 = -12 – 22 + 32 – 42 + 52 – 62 + 72 + 82 – 92
2) 9 = +12 – 22 – 32 + 42 – 52 – 62 + 72 – 82 + 92
3) 9 = +12 + 22 – 32 – 42 + 52 + 62 – 72 – 82 + 92
4) 9 = +12 + 22 + 32 + 42 – 52 + 62 – 72 – 82 + 92
==Rezolvare==
def solve_plus_minus(n, signs, current_sum, current_expression, result):
    if len(current_expression) == n:
        if current_sum == 0:
            result.append(" ".join(current_expression))
        return

    for sign in signs:
        new_sum = current_sum + sign * (current_expression[-1] + 1) ** 2
        if new_sum <= n:
            solve_plus_minus(n, signs, new_sum, current_expression + [sign], result)

def plus_minus(n):
    signs = [-1, 1]  # -1 pentru minus, 1 pentru plus
    result = []

    # Inițial, începem cu primul termen, care este întotdeauna un plus
    solve_plus_minus(n, signs, 1, [1], result)

    if not result:
        result.append("IMPOSIBIL")

    return result

# Citim input-ul
with open("plusminus.in", "r") as f:
    n = int(f.readline().strip())

# Calculăm rezultatul
result = plus_minus(n)

# Scriem rezultatul în fișierul de ieșire
with open("plusminus.out", "w") as f:
    for line in result:
        f.write(line + "\n")