Backtrack - Liệt kê hoán vị

Bài toán

Liệt kê tất cả các hoán vị của dãy số 1..n.

Độ phức tạp

O(n.n!)

Code này của Nguyễn Tiến Trung Kiên.

#include <stdio.h>

int n;

bool used[123];

int a[123];

void show() {

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

        printf("%d ", a[i]);

    printf("\n");

}

void back(int pos) {

    if (pos == n + 1) {

        show();

        return;

    }

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

        if (not used[i]) {

            a[pos] = i;

            used[i] = true;

            back(pos + 1);

            used[i] = false;

        }

}

int main() {

    scanf("%d", &n);

    back(1);

    return 0;

}

Nhận xét

Mô tả

int a[]

mảng này chứa các phần tử đang được xây dựng.

void show()

in ra mảng a.

bool used[]

used[i]=true nếu giá trị i đã được sử dụng trước đó.

void back(int pos)

gọi hàm này với mục đích là đang đứng ở vị trí pos, cần đặt cho a[pos] một giá trị mà chưa được sử dụng, sau đó gọi lời gọi tới hàm back(pos+1).

Các lỗi thường gặp

Runtime error

- Do quên không xét trường hợp pos=n+1

- Do quên không return trong trường hợp pos=n+1.

Wrong answer

- Do thiếu mất lệnh used[i]=false, nhớ rằng sau khi gọi hàm back con, phải "undo" lại cái quyết định của mình.

- Do không kiểm tra điều kiện if (not used[i]).

Đánh giá

Các bạn có thể đánh giá bài viết, yêu cầu giải thích hoặc gửi nhận xét tại đây.

http://goo.gl/forms/NrDT889TkK