Tìm tất cả các tập con của dãy n phần tử

[nguyenquibk1996 (Ngoc Qui)]

Em có bài toàn này mong mọi người giúp đỡ
Lập trình C++
TÌM TẤT CẢ CÁC TẬP CON CỦA DÃY N PHẦN TỬ VỚI N NHẬP TỪ BÀN PHÍM: 1, 2, 3, …, n

[rogp10]

Bài này là bài kinh điển của quay lui/pp sinh, bạn chịu khó google nhé nhiều lắm.

[nguyenquibk1996 (Ngoc Qui)]

mình tìm 1 lúc rồi mà k thấy source code cho bài toán này, bạn biết ko cho mình xin để đọc

[Nguyen_Thanh_Hai (Wake Of GOD)]

Có phải bài này là liệt kê ra tập con k của n phần tử ( k <= n ) không?
Bạn có thể tham khảo:

Simple Code C Java: [Bài toán] Liệt kê tập con của tập n phần tử.

[anhhuu (Phạm Minh Anh Hữu)]

Bài này đúng ra phải là tìm tất cả các tập con k phần tử từ n phần tử chứ, còn như đề của bạn thì chỉ có 1 tập con duy nhất là: 1, 2, 3,..., n
Và với đề đó, làm theo phương pháp sinh thì:

#include <iostream>

int main() {
	int *element= NULL; //Mảng lưu cấu hình
	int n, k;
	std::cout << "Nhap n: ";
	std::cin >> n;
	std::cout << "Nhap k: ";
	std::cin >> k;
	element= new int[k];
	for(int j = 0; j < k; j++)
        element[j] = j+1; //Set cấu hình ban đầu là 1,2,...,k

    std::cout << "Cac tap con la:\n";
	int index = 0;
	do {
		for(int j = 0; j < k; j++)
			std::cout << element[j]; //In tập con vừa tìm được
		std::cout << std::endl;
		index = k-1;

        //Đoạn bên dưới là sinh các tập hợp theo thứ tự từ điển
		while((index >= 0) && (element[index] == n - k + index + 1))
			index--;

		if(index >= 0) {
			element[index]++;
			for(int j = index+1; j < k; j++)
				element[j] = element[j-1] + 1;
		}
	}while (index != -1);
	delete[] element;
	return 1;
}

[anhhuu (Phạm Minh Anh Hữu)]

Các thuật toán kiểu này bạn nên đọc trong quyển Giải Thuật Và Lập Trình - Lê Minh Hoàng

[Quan_Nguyen_Dinh (Học AI.)]

dù biết bài hỏi lâu rồi nhưng vẫn để code của mình ở đây cho các bạn đến sau tham khảo:

#include <stdio.h>
void try(int i, int m, int *s, int n) {
	int z;
	for(z=s[i-1] + 1; z<=n; z++) {
		s[i] = z;
		if(i==m) {
			int k;
			for(k=1; k<=m; k++) {
				printf("%d", s[k]);
			}
			printf("\n");
		}
		else {
			try(i+1, m, s, n);
		}
	}
}
int main()
{
	int n;
	printf("Nhap n: ");
	scanf("%d", &n);
	int s[n+1];
	s[0] = 0;
	int i;
	for(i=0; i<=n; i++) {
		printf("Cac tap con %d phan tu la:\n", i);
		try(1, i, s, n);
		printf("\n");
	}
	return 0;
}

[Anh_Vo_Van_Huynh (Anh Võ Văn Huỳnh)]

//tim tat ca tap con n vd: 0 1 2 => {0}; {1} ; {2} ; {0, 1} ; {0, 2} ; {1, 2} ; {0; 1; 2}
#include <iostream>
using namespace std;
int n;
int x[100];
int a[100];
int b[100];
void Printf(int k)
{
    for (int i = 1; i <= k; ++i)
    {
        cout<<x[i]<<" ";
    }
    cout<<endl;
}
void Try(int i)
{
    for (int j = i; j <= n; ++j)
    {
        if(b[j]==true)
        {
            x[i] = a[j];
            b[j] = false;
            if(i==i)Printf(i);
            Try(i+1);
            if(i!= 1) b[j]=true;
        }
    }
}
int main() {
    fill(b,b+sizeof(x)/sizeof(x[0]),1);
    cin>>n;
    for (int i = 1; i <= n; ++i)
    {
        cin>>a[i];
    }
    Try(1);
    return 0;
}