Liệt kê các tập con k phần tử của tập n phần tử bằng thuật toán Back Track

Xem lại lý thuyết thuật toán Back Track

>> Lý thuyết về thuật toán quay lui Back Track

Biểu diễn tập con k phần tử dưới dạng c1, c2,.., ck, trong đó 1< c1các giá trị đề cử cho ci là từ ci-1+ 1 cho đến n - k + i. Cần thêm vào c0 = 0. Các giá trị đề cử này mặc nhiên được chấp nhận mà không cần phải thêm điều kiện gì.

Chương trình cài đặt:

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#define MAX  100

int B[MAX], n, k, count = 0;

void Init(void){

 printf("\n Nhap n="); scanf("%d", &n);

 printf("\n Nhap k="); scanf("%d", &k);

 B[0] = 0;

}

void Result(void){

 int i; count++;

 printf("\n Tap thu %d:", count);

 for (i = 1; i <= k; i++){

  printf("%3d", B[i]);

 }

 getch();

}

void Try(int i){

 int j;

 for (j = B[i - 1] + 1; j <= (n - k + i); j++){

  B[i] = j;

  if (i == k) Result();

  else Try(i + 1);

 }

}

void main(void){

 clrscr();

 Init();

 Try(1);

}