subset.cpp

常用算法与数据结构原代码

// output all subsets of n elements

#include <iostream.h>

int flag[20];
int n;

template<class T>
void SubSet(T list[], int i)
{
	int j;

	if (i == n-1)
	{
		// output subset without element n
		flag[i] = 0;
		for (j=0; j<n; j++)
		{
			if (flag[j])
				cout << list[j] << " ";
		}
		cout << endl;
		
        // output subset with element n
		flag[i] = 1;
		for (j=0; j<n; j++)
		{
			if (flag[j])
				cout << list[j] << " ";
		}
		cout << endl;
		return;
	}

	// leave element i out
    flag[i] = 0;
    // generate all subsets with i out
    SubSet(list, i+1);
                
    // put element i into subset
    flag[i] = 1;
    // generate all subsets with i included
    SubSet(list, i+1);
}

void main(void)
{
	char a[] = {'a', 'b', 'c', 'd'};
	n = 4;
	cout << "The subsets of abcd are" << endl;
	SubSet(a, 0);
}