🎯 Mục tiêu bài học

• Hiểu backtracking là gì: ta xây dựng lời giải dần dần theo từng bước.
• Biết sinh ra tất cả các hoán vị (permutation) 1..n.
• Biết sinh ra tổ hợp (combination) k phần tử từ n phần tử.

📘 Tư duy quay lui cơ bản

Ta xây dựng lời giải dần dần. Mỗi bước:

1. Thử chọn một giá trị hợp lệ tiếp theo.
2. Đệ quy sang bước tiếp theo.
3. Quay lui (bỏ lựa chọn đó đi) để thử lựa chọn khác.

Ý tưởng này lặp đi lặp lại trong TỔNG HỢP, THỬ NGHIỆM, và GIẢI ĐỀ THI HSG.

💻 Ví dụ 1: sinh hoán vị 1..n

C++

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> cur;
vector<int> used;

void backtrack() {
    if ((int)cur.size() == n) {
        for (int x : cur) cout << x << " ";
        cout << "\n";
        return;
    }
    for (int val = 1; val <= n; val++) {
        if (!used[val]) {
            used[val] = 1;
            cur.push_back(val);
            backtrack();
            cur.pop_back();
            used[val] = 0;
        }
    }
}

int main() {
    cin >> n;
    used.assign(n+1, 0);
    backtrack();
}

Python

n = int(input())
cur = []
used = [False]*(n+1)

def backtrack():
    if len(cur) == n:
        print(*cur)
        return
    for val in range(1, n+1):
        if not used[val]:
            used[val] = True
            cur.append(val)
            backtrack()
            cur.pop()
            used[val] = False

backtrack()

💻 Ví dụ 2: sinh tổ hợp C(n, k)

Chỉ chọn đúng k phần tử tăng dần, không lặp lại.

Python (tổ hợp)

n, k = map(int, input().split())
cur = []

def backtrack(start):
    if len(cur) == k:
        print(*cur)
        return
    for val in range(start, n+1):
        cur.append(val)
        backtrack(val+1)
        cur.pop()

backtrack(1)

🧩 Bài tập luyện tập

1. In tất cả các hoán vị của [1..n] theo thứ tự từ điển.
2. In tất cả tổ hợp k phần tử từ [1..n].
3. In tất cả chuỗi nhị phân độ dài n (gồm 0 và 1).

n = int(input())
cur = []
def backtrack():
    if len(cur) == n:
        print("".join(cur))
        return
    for bit in ["0","1"]:
        cur.append(bit)
        backtrack()
        cur.pop()
backtrack()