Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.8 kB
0
Indexable
Never
#include <iostream>

using namespace std;

const int TACKSIZE = 100000;

struct Stack {
	int top;
	int stack[TACKSIZE];

	Stack() {
		top = -1;
	}

	bool isEmpty() {
		return top == -1;
	}

	bool isFull() {
		return top == TACKSIZE - 1;
	}

	void push(int x) {
		if (this->isFull()) {
			cout << "Stack is filled, cannot push any more" << endl;
			return;
		}

		top++;
		stack[top] = x;
	}

	int pop() {
		if (this->isEmpty()) {
			cout << "Already empty, nothing to pop" << endl;
			return NULL;
		}

		top--;
		return stack[top + 1];
	}

	int peek() {
		if (this->isEmpty()) return NULL;
		return stack[top];
	}

	void printStack() {
		cout << "Tail to head: ";
		for (int i = 0; i <= top; i++)
		{
			cout << stack[i] << " ";
		}
		cout << endl;
	}
};

int t, rawt;
int total, n;
int numList[101];
Stack solu;

int solCount; //solution count

void resetNumberList() {
	for (int i = 0; i < 101; i++)
	{
		numList[i] = 0;
	}
}

void getInput() {
	cin >> total >> n;
	int drap;
	resetNumberList();
	for (int i = 0; i < n; i++)
	{
		cin >> drap;
		numList[drap]++;
	}
}

void sumItUp(int pos, int curSum) {
	//cout << pos << " " << curSum << endl;
	if (curSum > total) return;
	if (curSum == total) {
		solu.printStack();
		cout << endl;
		solCount++;
		return;
	}

	for (int i = pos; i < 101; i++)
	{
		if (numList[i] == 0) continue;
		if (curSum + i > total) break;

		solu.push(i);
		numList[i]--;
		sumItUp(i, curSum + i);
		numList[i]++;
		solu.pop();
	}
}

int main() {
	//freopen("input.txt", "r", stdin);
	cin >> t;
	rawt = t;
	
	while (t--)
	{
		getInput();

		solCount = 0;

		sumItUp(0, 0);


		cout << "#" << rawt-t << " ";
		if (solCount == 0) cout << -1;
		else cout << solCount;
		cout << "\n";
	}
}