Problemă backtracking Bacalaureat sesiunea august 2001, varianta 1

Enunț

Șiruri de cifre cu cifrele 1,2,3,4

Să se genereze toate șirurile formate din n cifre, fiecare șir generat având următoarele proprietăți:
- conține numai cifre din mulțimea {1, 2, 3, 4};
- orice două cifre alăturate sunt fie ambele pare, fie ambele impare.
Numărul natural n (3 ≤ n ≤ 15) se citește de la tastatură. Toate soluțiile vor fi scrise una după alta, cu spații între ele, fiecare șir fiind scris fără spații între cifrele ce-l formează. De exemplu, pentru n=3, se afișează (nu neapărat în această ordine) șirurile: 111, 113, 131, 311, 311, 313, 331, 333, 222, 224, 242, 244, 422, 424, 442, 444.

Cod sursă

#include <iostream>
using namespace std;

void back(int K, int N, int Sol[])
{
    if (K >= N)
    {
        for (int i = 0; i < N; ++i)
        {
            cout << Sol[i];
        }
        cout << endl;
        return;
    }


    for (int i = 1; i <= 4; ++i)
    {
        if (K >= 1)
        {
            if (Sol[K - 1] % 2 == i % 2)
            {
                Sol[K] = i;
                back(K + 1, N, Sol);
            }
        }
        else
        {
            Sol[K] = i;
            back(K + 1, N, Sol);
        }
    }
}

int main()
{
    int N, Sol[16];

    cin >> N;

    back(0, N, Sol);

    return 0;
}

Schema funcției backtracking back din codul de mai sus

O altă idee de rezolvare

Dacă toate perechile de cifre alăturate sunt fie pare, fie impare, toate cifrele din fiecare număr rezultat sunt pare, sau impare. În mulțimea {1, 2, 3, 4} sunt 2 numere pare și 2 numere impare. Mai întâi generăm șirurile formate după regulă de mai sus din mulțimea {1, 3} (numerele impare) și apoi {2, 4} (numerele pare). Pentru această soluție, modificăm doar funcțiile back și main să arate astfel:

void back2(int K, int N, int P[], int Sol[])
{
    if (K >= N)
    {
        for (int i = 0; i < N; ++i)
        {
            cout << Sol[i];
        }
        cout << endl;
        return;
    }

    Sol[K] = P[0];
    back(K + 1, N, Sol);
    Sol[K] = P[1];
    back(K + 1, N, Sol);
}

int main()
{
    int N, Sol[16], P[2];

    cin >> N;

    P[0] = 1;
    P[1] = 3;
    back2(0, N, P, Sol);

    P[0] = 2;
    P[1] = 4;
    back2(0, N, P, Sol);

    return 0;
} 

Schema funcției backtracking (modificată) back2