计算直线的交点数 [dfs]

Description 平面上有n条直线，且无三线共点，问这些直线能有多少种不同交点数。 比如,如果n=2,则可能的交点数量为0(平行)或者1(不平行)。

Input 输入数据包含多个测试实例,每个测试实例占一行,每行包含一个正整数n（n<=20）,n表示直线的数量.

Output 每个测试实例对应一行输出，从小到大列出所有相交方案，其中每个数为可能的交点数,每行的整数之间用一个空格隔开。

Sample Input 2 3

Sample Output 0 1 0 2 3

代码

注意要去除重叠的答案

#include<stdio.h> #include<math.h> #include<algorithm> #define MAX_N 400 using namespace std; int res[MAX_N]; int N,n; void dfs(int cnt,int top,int last){ if(last==0){ res[N++]=cnt/2; return ; } if(last<0) return ; for(int i=top;i>0;i--){ dfs(cnt+i*(n-i),i,last-i); } } int main() { while(scanf("%d",&n)!=EOF){ N=0; dfs(0,n,n); sort(res,res+N); for(int i=0,l=-1;i<N;i++){ if(l!=res[i]) { if(i) putchar(' '); printf("%d",res[i]); l=res[i]; } } putchar('\n'); } return 0; }