Hiểu bài toán

Cho một số nguyên dương n (1 ≤ n ≤ 9), yêu cầu liệt kê tất cả các hoán vị của tập hợp A = {1, 2, ..., n}. Các hoán vị cần được in ra theo thứ tự từ điển tăng dần, mỗi hoán vị trên một dòng, các số cách nhau bởi dấu cách.

Các cách tiếp cận

Cách Quay lui (Backtracking) - Duyệt theo thứ tự tự nhiên

#include <stdio.h>
#include <stdbool.h>

int n;
int permutation[10];
bool used[10]; // Mảng đánh dấu các số đã được sử dụng

void print_permutation() {
    for (int i = 0; i < n; i++) {
        printf("%d", permutation[i]);
        if (i < n - 1) printf(" ");
    }
    printf("\n");
}

// k là chỉ số vị trí đang điền (từ 0 đến n-1)
void generate_permutations(int k) {
    if (k == n) { 
        print_permutation();
        return;
    }

    // Thử các số từ 1 đến n vào vị trí k
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            permutation[k] = i; // Chọn
            used[i] = true;     // Đánh dấu
            generate_permutations(k + 1); // Gọi đệ quy
            used[i] = false;    // Quay lui (bỏ đánh dấu)
        }
    }
}

int main() {
    scanf("%d", &n);
    generate_permutations(0);
    return 0;
}

• Time Complexity: O(n! * n)
• Space Complexity: O(n)

Đây là phương pháp cơ bản và trực quan nhất. Hàm generate_permutations(k) có nhiệm vụ điền giá trị vào vị trí thứ k của hoán vị.

• Cơ sở: Nếu k == n (đã điền đủ n phần tử), ta in ra hoán vị hiện tại.
• Quy trình: Duyệt qua các số i từ 1 đến n. Nếu số i chưa được sử dụng:
  1. Gán permutation[k] = i.
  2. Đánh dấu used[i] = true.
  3. Gọi đệ quy cho vị trí tiếp theo: generate_permutations(k + 1).
  4. (Quay lui) Bỏ đánh dấu used[i] = false để có thể sử dụng i cho các nhánh khác.

Phương pháp này sinh ra các hoán vị theo đúng thứ tự từ điển tăng dần do vòng lặp for chạy từ số nhỏ đến số lớn.

Cách Quay lui (Backtracking) - Phiên bản biến thể

#include <stdio.h>
#include <string.h>

int n;
int Hoanvi[10];
int used[10];

void QuayLui(int i) {
    // i là chỉ số đang điền (từ 1 đến n)
    for (int j = 1; j <= n; j++) {
        if (used[j] == 0) { 
            used[j] = 1;
            Hoanvi[i] = j;

            if (i == n) {
                for (int k = 1; k <= n; k++) {
                    printf("%d ", Hoanvi[k]);
                }
                printf("\n");
            } else {
                QuayLui(i + 1);
            }

            used[j] = 0;
        }
    }
}

int main() {
    scanf("%d", &n);
    memset(used, 0, sizeof(used));
    QuayLui(1);
    return 0;
}

• Time Complexity: O(n! * n)
• Space Complexity: O(n)

Đây là biến thể của phương pháp quay lui, thường thấy trong các bài toán liệt kê hoán vị.

• Tham số i đại diện cho độ dài của tiền tố (prefix) đã được xây dựng.
• Vòng lặp j duyệt các số từ 1 đến n để thử vào vị trí i.
• Điều kiện dừng là khi i == n.

Về bản chất, logic hoạt động tương tự Approach 1. Việc sử dụng chỉ số từ 1 đến n (thay vì 0 đến n-1) là một cách cài đặt khác, nhưng vẫn đảm bảo thứ tự từ điển.

Cách Quay lui với Mảng Đánh Dấu (Backtracking with Boolean Array)

#include <stdio.h>
#include <stdbool.h>

int n;
int a[20];
bool used[20];

void btr(int k) {
    if (k == n) {
        for (int i = 0; i < n; i++) {
            printf("%d ", a[i]);
        }
        printf("\n");
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            a[k] = i;
            used[i] = true;
            btr(k + 1);
            used[i] = false;
        }
    }
}

int main() {
    scanf("%d", &n);
    btr(0);
    return 0;
}

• Time Complexity: O(n! * n)
• Space Complexity: O(n)

Đây là cách diễn đạt code gọn gàng và chuẩn mực nhất trong các solution.

• Mảng a[] lưu hoán vị hiện tại.
• Mảng used[] (kiểu bool) lưu trạng thái các số đã dùng. Việc dùng bool giúp code rõ ràng hơn int (0/1).
• Hàm btr(k) thực hiện递归 (đệ quy) để điền vào vị trí k.

Đây là推荐 (khuyến nghị) implementation cho các bài toán hoán vị cơ bản.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Sử dụng đệ quy kết hợp mảng đánh dấu (used array) là cách hiệu quả nhất để sinh hoán vị trong lập trình thi đấu.
• Thứ tự xuất hiện của các hoán vị phụ thuộc hoàn toàn vào thứ tự duyệt của vòng lặp for: duyệt từ nhỏ đến lớn sẽ sinh ra thứ tự từ điển tăng dần.

Lỗi thường gặp

• Quản lý trạng thái (State Management): Quên khôi phục giá trị biến trạng thái (mảng used) sau khi đệ quy xong là lỗi quay lui (backtracking) thường gặp nhất.
• Lỗi in ấn: In thừa dấu cách cuối dòng hoặc in thiếu newline.
• Biên độ (Constraints): Với n <= 9, giải pháp O(n!) là tối ưu. Tuy nhiên, nếu n lớn hơn, cần các thuật toán khác (như Steinhaus-Johnson-Trotter).