#include <bits/stdc++.h>

using namespace std;

int n;

int a[100];

void printResult(){

    for(int i=0; i<n; i++)

        cout << a[i];

    cout << endl;

}

void backtracking(int i){

    if(i >= n){

        printResult();

        return;

    }

    for(int j=0; j<=1; j++){

        a[i] = j;

        backtracking(i+1);

    }

}

int main(){

    cin >> n;

    backtracking(0);

    return 0;

}

3

000

001

010

011

100

101

110

111

#include <bits/stdc++.h>

using namespace std;

int n;

int a[100];

bool use[100]; //use[i] : kiểm tra số i đã sử dụng chưa?

void printResult(){

    for(int i=0; i<n; i++)

        cout << a[i];

    cout << endl;

}

void backtracking(int i){

    if(i >= n){

        printResult();

        return;

    }

    for(int j=1; j<=n; j++){

        if(use[j] == false){

            use[j] = true;

            a[i] = j;

            backtracking(i+1);

            use[j] = false;

        }

    }

}

int main(){

    cin >> n;

    backtracking(0);

    return 0;

}

3

123

132

213

231

312

321

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

int a[11][11];

int cnt;

bool solve;

void printAns(){

    cout << endl;

    for(int i=1; i<=9; i++){

        for(int j=1; j<=9; j++){

            cout << a[i][j] << " ";

            if(j%3 == 0) cout << " ";

        }

        cout << endl;

        if(i%3 == 0) cout << endl;

    }

}

// tra ve cac so chua duoc su dung

vector<int> select(int r, int c){

    //mang num dung de danh dau nhung so da duoc su dung tren hang ngang, doc, o 3x3

    bool num[11];

    memset(num, false, sizeof num);

    vector<int> v;

    // kiem tra hang va cot

    for(int i=1; i<=9; i++){

        num[a[r][i]] = true;

        num[a[i][c]] = true;

    }

    // kiem tra o 3x3

    int regionRow = (r-1)/3;

    int regionCol = (c-1)/3;

    for(int i=regionRow*3 + 1; i <= (regionRow+1)*3; i++){

        for(int j=regionCol*3 + 1; j <= (regionCol+1)*3; j++){

            num[a[i][j]] = true;

        }

    }

    // them cac so chua duoc chon vao mang

    for(int i=1; i<=9; i++){

        if(!num[i]) v.pb(i);

    }

    return v;

}

void dfs(int c){

    if(solve) return;

    // c >= 81 tuc la da dien het tat ca 81 o tren bang sudoku 9x9

    if(c >= 81){

        printAns();

        solve = true;

        return;

    }

    for(int i=1; i<=9; i++){

        for(int j=1; j<=9; j++){

            if(a[i][j] == 0){

                vector<int> vec = select(i, j);

                for(int k=0; k<vec.size(); k++){

                    a[i][j] = vec[k];

                    dfs(c+1);

                    a[i][j] = 0;

                }

                return;

            }

        }

    }

}

int main(){

    // so 0 bieu hien o do chua co gi

    for(int i=1; i<=9; i++)

        for(int j=1; j<=9; j++) {

            cin >> a[i][j];

            if(a[i][j]) cnt++;

        }

    dfs(cnt);

    if(!solve) cout << "Chiu roi!";

}

1 2 3 4 0 6 7 8 9

4 5 8 0 2 9 1 3 0

6 7 9 3 8 1 2 0 4

2 1 4 5 3 7 6 9 8

0 9 5 8 6 0 4 1 7

8 6 7 1 0 4 3 2 5

7 3 1 0 4 5 8 6 2

5 4 6 0 1 8 9 7 0

9 8 2 6 7 3 5 0 1

Result:

1 2 3  4 5 6  7 8 9

4 5 8  7 2 9  1 3 6

6 7 9  3 8 1  2 5 4

2 1 4  5 3 7  6 9 8

3 9 5  8 6 2  4 1 7

8 6 7  1 9 4  3 2 5

7 3 1  9 4 5  8 6 2

5 4 6  2 1 8  9 7 3

9 8 2  6 7 3  5 4 1

0 5 0 0 1 0 0 9 8

8 0 2 5 6 0 4 0 7

1 0 9 0 3 8 0 6 2

0 1 5 2 7 3 6 8 0

4 0 3 6 0 1 7 0 5

2 6 7 0 4 0 0 3 0

5 9 0 3 8 7 2 0 6

3 0 4 0 5 6 0 7 1

0 7 8 0 2 4 0 5 0

Result:

7 5 6  4 1 2  3 9 8

8 3 2  5 6 9  4 1 7

1 4 9  7 3 8  5 6 2

9 1 5  2 7 3  6 8 4

4 8 3  6 9 1  7 2 5

2 6 7  8 4 5  1 3 9

5 9 1  3 8 7  2 4 6

3 2 4  9 5 6  8 7 1

6 7 8  1 2 4  9 5 3