3917 - Numere 1234

Cerința

Se citește n număr natural nenul. Afișați în ordine crescătoare toate numerele care au o cifră egală cu 1, două cifre de 2, …, n cifre egale cu n.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran pe linii separte numerele cerute.În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• 1 ≤ n ≤ 4

Exemplul 1:

Intrare

2

Ieșire

122
212
221

Exemplul 2:

Intrare

5

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

def afisare(x, m):
    for i in range(1, m + 1):
        print(x[i], end="")
    print()

def valid(x, k, n):
    vf = [0] * 5
    for i in range(1, k + 1):
        vf[x[i]] += 1
    for i in range(1, n + 1):
        if vf[i] > i:
            return False
    return True

def backtracking(x, k, n, m):
    if k > m:
        afisare(x, m)
    else:
        for i in range(1, n + 1):
            x[k] = i
            if valid(x, k, n):
                backtracking(x, k + 1, n, m)

def check_restriction(n):
    return 1 <= n <= 4

def main():
    n = int(input())
    if not check_restriction(n):
        print("Datele nu corespund restrictiilor impuse")
        return
    
    m = n * (n + 1) // 2
    x = [0] * 11
    backtracking(x, 1, n, m)

if __name__ == "__main__":
    main()