UVA 11205 - The broken pedometer

题目大意：题中给了一种例子，LED的七根灯管不同的开关方式显示0到9的数字。其中可以去掉第六根灯管（可能去掉其他也可以，没细究）也就是只要六根灯管就可以区分所有的数字。简单理解可以认为是7位的一个二进制数，每个字符有不同的二进制数。开为1，关为0。最少需要几个位可以区分所有字符。输入r，l。r代表几位的二进制，l代表有几个字符。

解题思路：用子集生成的增量构造法。这是一个可以求一个集合所有集合的方法。我们对每一个子集都对应二进制的位，算出只取这些位计算出的每个字符的二进制数的大小是否都不一样。都不一样代表这个子集的元素数就可以是需要的位。

ac代码：

#include <iostream>
#include <cmath>
#include <set>
using namespace std;
int n, r, l, pu[105][105], a[105], len;
set <int>se;
void print_subset(int cur)
{
	se.clear();
	int sum, minu;
	for (int i=0; i<l; i++){
		sum = 0;
		for (int j=0; j<cur; j++)
			sum += pu[i][ a[j] ] * pow(2, a[j]);
		if (!se.count(sum))
			se.insert(sum);
	}
	if (se.size() == l && cur < len)
		len = cur;		
	if (cur)
		minu = a[cur-1] + 1;
	else
		minu = 0;
	for (int i=minu; i<r; i++){
		a[cur] = i;
		print_subset(cur+1);
	}
}
int main()
{
	scanf("%d", &n);
	while (n--){
		scanf("%d%d", &r, &l);
		len = r;
		for (int i=0; i<l; i++)	
			for (int j=0; j<r; j++)
				scanf("%d", &pu[i][j]);
		print_subset(0);
		printf("%d\n", len);
	}
return 0;
}