HOUSES.cpp

#include <iostream>
using namespace std;

const int MAX = 105;

int N;                  // Số người muốn mua nhà
int L;                  // Số lượng ngôi nhà
int a[MAX];             // Biểu diễn rằng : người thứ i sẽ mua a[i] ngôi nhà
int r[MAX];             // Mảng lưu kết quả
int SoldHouses;         // Tổng số ngôi nhà được mua
int FreeHouses;         // Tổng số ngôi nhà sẽ không được mua
int NumAnswer;          // Đếm số kết quả
bool Visit[MAX];        // Đánh dấu xem người thứ i đã mua hay chưa

/*
* idHouse: id ngôi nhà đang xét
* IgnoreHouses: tổng số những ngôi nhà đã bị bỏ qua, không bán
*/
void Check(int idHouse, int IgnoreHouses)
{
	// Nếu đã đủ 1000 kết quả thì return
	if(NumAnswer == 1000) return;
	
	// Nếu duyệt đến cuối cùng mà số nhà đã được bán hết thì ta được 1 kết quả
	if(idHouse >= L + 1)
	{
		NumAnswer++;
		for(int i = 1; i <= L; i++)
			cout << r[i] << " ";
		cout << endl;
		return;
	}

	// Không bán
	if(idHouse > 1 && IgnoreHouses < FreeHouses) Check(idHouse + 1, IgnoreHouses + 1);

	// Bán
	// Lần lượt bán cho người thứ i đến người thứ n
	for(int i = 1; i <= N; i++)
		if(!Visit[i])
		{
			Visit[i] = true;
			for(int j = 0; j < a[i]; j++)
				r[idHouse + j] = i;

			Check(idHouse + a[i], IgnoreHouses);

			for(int j = 0; j < a[i]; j++)
				r[idHouse + j] = 0;
			Visit[i] = false;
		}
}

int main()
{
	ios::sync_with_stdio(false);
	//freopen("input.txt","r",stdin);

	// Nhập đầu vào
	cin >> L >> N;

	SoldHouses = 0;
	for(int i = 1; i <= N; i++)
	{
		cin >> a[i];
		SoldHouses += a[i];
		Visit[i] = false;
	}

	FreeHouses = L - SoldHouses; 
	NumAnswer = 0;

	// Xét các trường hợp
	Check(1, 0);

	return 0;
}