Find k-distinct partitions which contain at least two perfect squares 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&lt;N&lt;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 &lt;stdio.h&gt;
#include &lt;math.h&gt;

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",&amp;n,&amp;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&lt;k;i++){
            sum=sum+a[i];
        }
        if(sum==n){
            for(i=0;i&lt;k;i++){
                if(perfect(a[i])){
                    perf++;
                }
            }
            if(perf&gt;=2){
                count++;
            }
        }
    }
    else{
        a[index]=val;
        for(i=a[index];a[index]&lt;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;
}
This is an interesting challenge! Here are some ways you could improve your code.

Globals

None of your variables should be global. It makes it significantly harder to figure out where a variable is changing. Given that you reset sum and perf to 0 every time you enter func(), they should be locally declared within the function. i is only used within func() as well. You should prefer declaring variables as close to their first use as possible to make it easier to find the declaration. For loops, it's often best to declare them in the loop like this:

for (int i = 0 ; i &lt; k; i++) {
    ...
}


This also avoids problems that can occur with re-using loop index variables. Notice that you assign to i at the start of the last loop in func(), but then it is never incremented or checked in that loop. It's entirely superfluous, and confusing to read.

func() should return a count rather than incrementing a global variable. For example you could make a local variable and use it like this:

int func(int index, int val) {
    int numPerfectPartitions = 0;
    if (index == k) {
        ...
        if (sum == n) {
            ...
            if (perf &gt;= 2) {
                numPerfectPartitions++;
            }
        }
    }
    else {
        a[index]=val;
        for (...) {
            numPerfectPartitions += func(index + 1, a [ index ] + 1);
        }
    }
    return numPerfectPartitions;
}


Naming

I feel like your names are too vague. perfect() is OK. I would name it isPerfect() just to be more clear, and since it returns what is essentially a Boolean value.

n and k match the text of the challenge, but are bad variable names. I recommend changing n to desiredSum since that's the target number you're trying to reach. (Or even target.) I would name k numPartitions since that's the number of partitions.

a is probably best called something like addends or summands. This is a case where there's no real-world analog, so the names get a little technical. But a is just too vague.

count is an OK name, but what is it a count of? numFound would be better.

func() tells you literally nothing other than that the function is a function, which anyone who can read C already knows. Since it finds partitions, why not call it findPartitions()?

Performance

I'll admit that I don't know off the top of my head of a significantly better way to do this. I suspect that if you first found the perfect squares between 1 and n, then you could find the partitions more quickly. For example, generate all perfect squares between 1 and n, and then find all combinations of 2 through k of the perfect squares that sum to less than or equal to n. Subtract that sum from n to find a new, smaller sum m, and then generate all combinations of the remaining (non-perfect-square) numbers that sum to m. Since you're summing to a smaller value, you should have fewer permutations to go through.