Program to print all combinations of numbers whose square equal to given number

Question

#include <stdio.h>

void printCombs(int n) {
    int i, j, limit = ceil(sqrt(n));
    for(i = 1; i < limit; i++) {
        for(j = i; j < limit; j++) {
            if(i*i + j*j == n) {
                printf("%d,%d\n", i, j);
                printf("%d,", j);
                printCombs(i*i);
                printf("\n%d,", i);
                printCombs(j*j);    
                printf("\n");
            }
        }
    }
}

int main() {

    int n;
    scanf("%d", &n);

    printCombs(n);

    return 0;
}

I have written this code which outputs combinations of numbers whose sum of squares equals the given input. The code is working fine but the problem is with the not-wanted output.

For example I enter 1000:

1000
10,30
30,6,8
8,
6,

10,18,24
24,
18,

18,26
26,
18,10,24
24,6,8
8,
6,

10,

First I get 10,30 which is fine because 100+900 = 1000.

Then 30, 6, 8 => 900+36+64 = 1000.

Then 10, 18, 24 => 100 + 324 + 576 = 1000.

Then 18, 26 => 324 + 676 = 1000.

Then 18, 10, 24 => 576 + 100 + 324 = 1000.

Now these are all the combinations. But as you can see there are some other number output also on the screen which are due to the printf() before the recursive calls which do not output anything. And in the end when it outputs 24, 6, 8.`. I am not being able to figure out how to prevent this from output-ing. How do I just print those combinations? Any help is appreciated thanks.

passing "prefix" to your function seems the simpler.(to get rid of printf("%d,", j);, you would need sprintf). — Jarod42
But your algo can miss some combination: 3 = 1²+1²+1² but cannot be written as a²+b²... — Jarod42
@Jarod42 I know its not the question but only if you can guide me to a more general approach to this problem? I mean, I know that this can be done by applying nested loops so that every combination can be checked but how do I convert that into recursion? — Rumaisa Tahir

pmg pmg · Accepted Answer · 2018-10-21T16:44:49

Rather than printing little by little, try and print all numbers in one statement.

For that you may need to rewrite your function a little bit.

Here's my attempt

#include <math.h>
#include <stdio.h>

void printCombs2(int n, int k) {
    int limit = ceil(sqrt(n));
    for (int i = 1; i < limit; i++) {
        for (int j = i; j < limit; j++) {
            if (i*i + j*j == n) {
//                printf("%d, %d, %d\n", i, j, k);
                printf("%d, %d, %d ==> %d+%d+%d=%d\n", i, j, k, i*i, j*j, k*k, i*i+j*j+k*k);
            }
        }
    }
}

void printCombs(int n) {
    printf("combs(%d):\n", n);
    int limit = ceil(sqrt(n));
    for (int i = 1; i < limit; i++) {
        for (int j = i; j < limit; j++) {
            if (i*i + j*j == n) {
//                printf("%d, %d\n", i, j);
                printf("%d, %d ==> %d+%d=%d\n", i, j, i*i, j*j, i*i+j*j);
                printCombs2(i*i, j);
                printCombs2(j*j, i);
            }
        }
    }
    puts("");
}

int main(void) {
    printCombs(100);
    printCombs(1000);
    printCombs(10000);

    return 0;
}

see it running on ideone.com

combs(100):
6, 8 ==> 36+64=100

combs(1000):
10, 30 ==> 100+900=1000
6, 8, 30 ==> 36+64+900=1000
18, 24, 10 ==> 324+576+100=1000
18, 26 ==> 324+676=1000
10, 24, 18 ==> 100+576+324=1000

combs(10000):
28, 96 ==> 784+9216=10000
60, 80 ==> 3600+6400=10000
36, 48, 80 ==> 1296+2304+6400=10000
48, 64, 60 ==> 2304+4096+3600=10000

Program to print all combinations of numbers whose square equal to given number

1 Answers