alg3.cpp

#include <stdio.h>
#include <conio.h>

using namespace std;

int n,k; // количество элементов в множестве
int a[20],res[20];  //a - массив для хранение исходного множества. res - массив для сгенерированных подмножеств

//рекурсивная фунцикя генерации подмножеств. генерирует все наборы из 0 и 1 длиной n такие, что содержат не больше чем k единиц
//например для n=4 k=2
//0000
//0001
//0010
//0100
//1000
//0011
//0101
//0110
//1001
//1010
//1100
//в каждом наборе 0 означает что элемент не попал в подмножество, 1 - что попал
void gen(int pos, int val,int sum) //pos - позиция/номер числа, val - 0 или 1, sum - сколько уже единиц
{
	if(sum>k) return; //если количество единиц уже больше k - то не продолжаем генерацию
	
	res[pos] = val; // записали в резульат
	if(pos==n-1) //если сгенерировали комбинацию 
	{
		if(sum==k) //проверяем если количество единиц ровно k , то выводим ее в ответ
		{
			printf("{ ");
			for(int i=0;i<n;i++) 
				if(res[i]==1) printf("%d ",a[i]); //в цикле по всем числам комбинации, если число = 1 значит выводим элемент
			printf("}");
			printf("\n");
		}
	}
	else	
	{
		gen(pos+1,0,sum); //вариант когда следующий элемент не берем в множество
		gen(pos+1,1,sum+1); //вариант когда следующий элемент берем в множество
	}
}

int main()
{
	scanf("%d %d",&n,&k); //вводим n - количество элементов , и число k
	for(int i=0;i<n;i++) scanf("%d",&a[i]); //вводим сами элементы
	gen(0,0,0);  //вариант когда нулевой элемент не берем в множество
 	gen(0,1,1);  //вариант когда нулевой элемент берем в множество
 	getch();
	return 0;
}