Description
小X学习了dfs，为了练习搜索，开始给自己出题玩。
玩着玩着，一会把自己难住了，一会又被自己难倒了，真是有趣诶！
小X出的题：
现在有N个不同的正整数，求它们可以组成多少个这样的集合，满足：
- 集合内的元素数量S>1
- 集合内任意两个数的差的绝对值都大于集合内的元素数量。
Input
第一行，一个正整数T(T<=20)表示数据组数。
对于每组数据，有两行。第一行为一个正整数N（3≤N≤25），第二行为N个用空格隔开的正整数xi(xi≤200)。
Output
对于每组数据，输出一行一个整数表示题中所描述的集合的个数。
Sample Input
1
5
2 3 5 8 1
Sample Output
6
Hint
{5,8},{1,5},{1,8},{2,5},{2,8},{3,8}.
用dfs搜索，依次枚举第i个数，当准备加入下一个数时，需要检查当前的最小间隔是否大于当前的集合数量+1，在dfs时，传递一个最小值即可进行判断。
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
#define INF 0x3fffffff
int a[50];
int ans, n;
void dfs(int pos,int dis,int gap)//dis表示数组中数字个数 gap表示任意两数之差的最小值 pos表示加入的数的位置
{
if (pos == n - 1 || gap <= dis + 2)return;
for (int i = pos+1; i < n; i++)
{
if (a[i] - a[pos]>dis + 2)
{
dfs(i, dis + 1, min(gap, a[i] - a[pos]));
ans++;
}
}
}
int main()
{
int T;
while (cin >> T)
{
while (T--)
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
ans = 0;
sort(a, a + n);
for (int i = 0; i < n; i++)
dfs(i, 0,INF);
printf("%d\n", ans);
}
}
return 0;
}
/**********************************************************************
Problem: 1973
User: leo6033
Language: C++
Result: AC
Time:84 ms
Memory:2024 kb
**********************************************************************/