Find k-distinct partitions which contain at least two perfect squares

Question

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;
}

Answer 1

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 < 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 >= 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.

Answer 2

Well, if you want k-distinct partitions with at least two distinct perfect squares, start with the perfect squares, intead of the partitioning. Anything else is too inefficient.

So, let's efficiently find them:

for i in perfect_squares up to N
    optionally remember i is prefect square here
    for j in perfect_squares up to min(i - 1, N - i)
        $rest = N - i - j
        Add number of (k-2)-distinct partitions of rest avoiding i and j
        ... where any element > i is not a perfect square

That is much better than linear, and thus very much preferable to your quadratic solution.

Now, let's look at your code:

1. Your code compiles very cleanly, kudos to you! The only thing are those two conversions in perfect(). Why don't you stay with double instead of moving to float? And consider being more explicit that you actually want the truncation when assigning to iVar.

2. Be aware that sqrt() is not generally guaranteed to be perfectly accurate, even if the result is exactly representable. Floating-point-arithmetic is a field for itself with unique dangers.

3. Globals. Don't use them unless you really have to, and even then take another look. They increase complexity enormously, as they can be potentially modified everywhere, they inhibit re-use and in multithreaded programs are prone to data-races.

4. Especially if you have a result, return it as a return-value, don't stash it in some arbitrary global.

5. Names are important. They are the first thing anyone trying to find or understand something will see, so don't waste that chance.

6. And if you combine the above three points, it's even more critical: Having the same Symbol without internal linkage defined in two separate TUs, unless it's inline and equivalent, is undefined behavior.
   That's a good reason to give things internal linkage with static, which also makes inlining more likely.

• func should be count_3part_2perfect or something like that and return the result.
• perfect should be is_perfect_square or alike. Well, actually you won't need it.
• I won't go into your variable-names, though they also merit improvement.

7. Consider defining your functions before you use them. Doing so allows you to dispose of the forward-declarations.

8. As an aside, since C99 return 0; is implicit for main(). Use it or don't.

9. Consider investing in a few more spaces. A single space after a comma, and single spaces around binary pperators (but neither . nor ->) makes Things less cramped and easier to scan.

10. I'm not sure that anti-pattern has a name, but anyway:

    if (comparison)
        return 1; // Or true
    else
        return 0; // Or false
    

    Should be simplified to:

    return comparison;
    

    If it's not a comparison or something else guaranteed to be 0/false or 1/true, you can use !!(expr) or similar to normalize it if wanted. Normalizing is often a waste though.

11. Seems you are in the camp of those religiously using curly braces everywhere. It's not a bad idea for beginners, though I personally dislike going quite that far.

Answer 3

You already have a good review of your code's style, so I'll discuss the performance here.

Currently, we find all the partitions of N, and count the perfect squares in each. What we could do instead is to start with two perfect squares, and count how many ways we can partition the remainder of N without using either of those initial square numbers.

Let's start with a loop that generates two distinct square numbers whose sum is less than n:

for (unsigned i = 1;  i*i < n/2;  ++i) {
    for (unsigned j = i + 1;  i*i + j*j < n;  ++j) {
        ...
    }
}

For each of these combinations, we need to count how many ways we can partition the remainder of n without using i*i or j*j. Let's write a simple function to do that:

/* return number of distinct k-partitions of n that don't contain skip1
   or skip2, and where all numbers are greater than start. */
unsigned int count_partitions(unsigned int n, unsigned int k,
                              unsigned int start,
                              unsigned int skip1, unsigned int skip2)
{
    if (k == 1) {
        /* base case - we have a single 1-partition, unless it's a
           number we've already used. */
        return n > start && n != skip1 && n != skip2;
    }

    unsigned count = 0;
    for (unsigned i = start+1;  i * k <= n;  ++i) {
        if (i == skip1 || i == skip2) continue;
        count += count_partitions(n-i, k-1, i, skip1, skip2);
    }
    return count;
}

Note that the limit for the loop is i * k <= n - since we know we'll be using k numbers at least the size of i, we can finish our loop relatively early.

You might be able to use your mathematical knowledge to reduce the recursion depth here (it's fairly easy to count the k=2 partitions - but remember to deal with skip1 and skip2 as appropriate).

---

Full program

/* return number of distinct k-partitions of n that don't contain skip1
   or skip2, and where all numbers are greater than start. */
unsigned int count_partitions(unsigned int n, unsigned int k,
                              unsigned int start,
                              unsigned int skip1, unsigned int skip2)
{
    unsigned count = 0;
    switch (k) {
    case 0:                     /* Allow for top-level k==2 */
        return n==0;
    case 1:
        /* recursion base - we have a single 1-partition, unless it's a
           number we've already used. */
        return n > start && n != skip1 && n != skip2;
    default:
        for (unsigned i = start+1;  i * k < n;  ++i) {
            if (i == skip1 || i == skip2) continue;
            count += count_partitions(n-i, k-1, i, skip1, skip2);
        }
        return count;
    }
}

/* return number of k-partitions of n containing two or more perfect
   squares. */
unsigned int count_2perfect_partitions(unsigned int n, unsigned int k)
{
    unsigned count = 0;
    for (unsigned i = 1;  i*i < n/2;  ++i) {
        for (unsigned j = i + 1;  i*i + j*j <= n;  ++j) {
            count += count_partitions(n - (i*i + j*j), k-2, 0, i*i, j*j);
        }
    }
    return count;
}

#include <stdio.h>    
int main()
{
    unsigned int n, k;
    if (scanf("%u,%u", &n, &k) != 2 || k < 2) {
        fprintf(stderr, "Input format error\n");
        return 1;
    }

    printf("%u\n", count_2perfect_partitions(n, k));
    return 0;
}

My timing results show about 1ms each for 12,3 and 150,30 (this latter trivially gives 0 as output, as triangle(30) > 150), and about 930ms for a more demanding test of 200, 10 (result 107,952,450);