[C++ Quay lui] Liệt kê hoán vị các số từ 1 đến n

Cho một tập hợp gồm n phần tử có giá trị từ 1 đến n. Yêu cầu xuất ra các hoán vị của tập hợp này theo thứ tự tăng dần.

Dữ liệu đầu vào: số nguyên dương n (n<10)
Dữ liệu đầu ra: gồm n! dòng ghi các hoán vị theo thứ tự tăng dần, mỗi phần tử của tập hợp ngăn cách nhau bởi khoảng trắng.

Ví dụ:
Input: 3
Output:
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

Code tham khảo

#include <iostream>
using  namespace std;

int n, kq[11], dd[10];

void xuat()
{
    for (int j=1; j<=n; j++)
        cout<< kq[j]<<" ";
    cout << endl;
}

void backtrack(int i)
{
    if (i>n) xuat();
    for (int j=1; j<=n; j++)
        if (dd[j]==0)
        {
            dd[j]=1;
            kq[i]=j;
            backtrack(i+1);
            dd[j]=0;
        }
}

int main()
{
    cin >> n;
    for (int i=1; i<=9; i++)
        dd[i]=0;
    backtrack(1);
}

 

One thought on “[C++ Quay lui] Liệt kê hoán vị các số từ 1 đến n

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *