Problem Statement:
A k-distinct-partition of a number \$n\$ is a set of \$k\$ distinct positive integers that add up to \$n\$. For example, the 3-distinct partitions of 10 are
\$1+2+7\$
\$1+3+6\$
\$1+4+5\$
\$2+3+5\$The objective is to count all k-distinct partitions of a number that have at least two perfect squares in the elements of the partition.
Note that 1 is considered a perfect square.
Constraints
\$k<N<200\$, so that at least one k-distinct partition exists.
Input Format
The input consists of one line containing of \$N\$ and \$k\$ separated by a comma.
Output
One number denoting the number of k-distinct partitions of N that have at least two perfect squares in the elements of the partition.
Explanation
Example 1
Input
10, 3
Output
1
Explanation: The input asks for 3-distinct-partitions of 10. There are 4 of them (1+2+7, 1+3+6, 1+4+5 and 2+3+5). Of these, only 1 has at least two perfect squares in the partition (1+4+5).
Example 2
Input
12, 3
Output
2
Explanation The input asks for 3-distinct partitions of 12. There are 7 of them (9+2+1, 8+3+1,7+4+1,7+3+2,6+5+1, 6+4+2, 5+4+3). Of these, two, (9+4+1, 7+4+1) have two perfect squares. Hence, the output is 2.
My code hangs when the numbers are big, e.g. when N = 150 and k = 30
The code
#include <stdio.h>
#include <math.h>
int a[200];
int count=0;
int n,k;
int i,sum,perf;
void func(int,int);
int perfect(int number);
int main()
{
scanf("%d,%d",&n,&k);
func(0,1);
printf("%d",count);
return 0;
}
void func(int index,int val){
sum=0,perf=0;
if(index==k){
for(i=0;i<k;i++){
sum=sum+a[i];
}
if(sum==n){
for(i=0;i<k;i++){
if(perfect(a[i])){
perf++;
}
}
if(perf>=2){
count++;
}
}
}
else{
a[index]=val;
for(i=a[index];a[index]<n;a[index]++){
func(index+1,a[index]+1);
}
}
}
int perfect(int number)
{
int iVar;
float fVar;
fVar=sqrt((double)number);
iVar=fVar;
if(iVar==fVar) return 1;
else return 0;
}