ch.cpp

求一个集合的子集的非递归解法

#define N 8

#include <iostream>
#include <stack>

using namespace std;

struct snode
{
	int cnt, pos;
	bool poped;
};

int main()
{
	stack<snode> sk;
	snode nod, nod1, nod2;
	bool b[N]; int subsetnum = 0;
	
	for(int k=1; k<=N; k++)
	{
		memset(b, false, N);
		nod.cnt=0; nod.pos=0; nod.poped = false;
		sk.push(nod);
		while(!sk.empty())
		{
			nod = sk.top();
			sk.pop();
			if(nod.cnt==k)
			{
				for(int j=0; j<nod.pos; j++)
					if(b[j]) cout << j << ",";
				cout << endl;
				subsetnum ++;
				continue;
			}
			if(nod.pos==N) continue;

			if(!nod.poped)
			{
				nod.poped = true;
				sk.push(nod);
			}
			else
			{
				nod.poped = false;
				b[nod.pos++] = false;
				sk.push(nod);
				continue;
			}

			if(nod.pos<N)
			{
				b[nod.pos++] = true;
				nod.poped = false;
				nod.cnt++;
				sk.push(nod);
			}
		}
	}
	cout << subsetnum+1 << endl;
	return 0;
}