Editing 1356 - N Sir

==Cerința==
Fie n un număr natural.
Să se determine toate șirurile a de k numere naturale nu neapărat distincte: 1 ≤ a1, a2,...,ak  ≤ n, astfel încât:
1) 1 = 1/a1+ 1/a2+...+ 1/ak
2) n = a1 + a2 +...+ ak

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

==Date de ieșire==
Fișierul de ieșire nsir.out va conține pe fiecare linie câte un șir determinat, în ordine lexicografică. Dacă nu poate fi generat un astfel de șir, atunci se va scrie valoarea 0 pe prima linie a fișierului de ieșire.

==Restricții și precizări==
5 ≤ n ≤ 75
se admite că cerința 1) este satisfăcută dacă: | 1/a1 + 1/a2 + … + 1/ak – 1 |<10-5
==Exemplu==:
nsir.in

33
nsir.out

3 3 9 9 9
3 5 5 5 15
==Explicație==
Se observă că
1) 1 = 1/3+1/3+1/9+1/9+1/9 și 33 = 3+3+9+9+9
2) 1 = 1/3+1/5+1/5+1/5+1/15 și 33 = 3+5+5+5+15
==Rezolvare==
def backtracking(n, k, target_sum, current_sum, current_sequence, result):
    if k == 0:
        if current_sum == target_sum:
            result.append(list(current_sequence))
        return

    for i in range(1, min(n, target_sum - current_sum) + 1):
        current_sequence.append(i)
        backtracking(n, k - 1, target_sum, current_sum + i, current_sequence, result)
        current_sequence.pop()


def find_sequences(n):
    result = []
    for k in range(2, n + 1):
        backtracking(n, k, n, 0, [], result)
    return result


if __name__ == "__main__":
    # Citim numărul n din fișierul de intrare
    with open("nsir.in", "r") as f:
        n = int(f.readline().strip())

    # Găsim și afișăm șirurile în fișierul de ieșire
    sequences = find_sequences(n)
    with open("nsir.out", "w") as g:
        if not sequences:
            g.write("0\n")
        else:
            for sequence in sequences:
                g.write(" ".join(map(str, sequence)) + "\n")
python nsir.py