Untitled
unknown
plain_text
2 years ago
1.8 kB
2
Indexable
#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"; } }
Editor is loading...