/*
 * Display all subsets of a given size from a master set
 *
 * Copyright 1994-1995 Dave Dunfield
 * All rights reserved.
 *
 * Permission granter for personal (non-commercial) use only.
 *
 * Compile command: cc subset -fop
 */
#include <stdio.h>

#define	SUBSET_SIZE	3		/* Size of subsets to display */
#define	ELEMENTS(array)	(sizeof(array)/sizeof(array[0]))

static char *set[] = { "balloon", "tree", "fish", "dog", "cat" };

/*
 * Display all subsets of 'm' elements which can be
 * found in 'set' of 'n' elements.
 */
showset(char *set[], int n, int m)
{
	int i, j;
	static int sp = 0;
	static char **subset;
	/* At top level entry, allocate memory for subset */
	if(!sp)
		subset = (char**)malloc(m*sizeof(char*));
	/* Walk set, compute subsets till we reach desired size */
	for(i=0; i < n;) {
		subset[sp++] = set[i++];	/* Add element to subset */
		if(sp == m) {				/* Correct size subset - print */
			for(j=0; j < sp; ++j)
				printf("%s ", subset[j]);
			printf("\n"); }
		else						/* Expand subset to the right */
			showset(&set[i], n-i, m);
		--sp; }
	/* At top level exit, release allocated memory */
	if(!sp)
		free(subset);
}

/*
 * main program to demo function
 */
main()
{
	showset(set, ELEMENTS(set), SUBSET_SIZE);
}