# Distinct Partition Squares

## Distinct Partition Squares

### Problem Description

Among the several path breaking contributions to Number theory by the famous Indian mathematician Srinivasa Ramanujan, his contribution to partitions is extensive and deep. A partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered the same partition. For example, 4 can be expressed as a sum of positive integers in the following ways: 1+1+1+1, 1+1+2, 1+3, 2+2, 4. Of these, only 1+3 and 4 use non repeating summands. Partitions using non repeating summands are called distinct partitions of n. There is no general formula for the number of partitions of an integer n and it is known that the partitions grow rapidly with n.

A k-distinct-partition of a number n is a set of k distinct positive integers that add up to n. For example, 3-distinct partitions of 10 are 1+2+7, 1+3+6,1+4+5 and 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.

answered Jul 26, 2018 by (340 points)
#include <stdio.h>

int c=0,x;
int s;
int check(int n)
{
int i,cn=0;
for(i=1;i<=n;i++)
{
if(i*i == n)
return 1;
}
return 0;
}
void sum(int k,int i,int m)
{
int j,cn=0,f=0,l;
if(k==0)
{
if(i<=m)
{
for(l=0;l<x-k-1;l++)
if(s[l]==m)
f=1;
if(f!=1)
{
s[x-k-1]=m;
for(i=0;i<x;i++)
{
cn+=check(s[i]);
}
if(cn>=2)
c++;
}
return;
}
}
else
{
if(i>m)
return ;
for(j=i;j<m;j++)
{
for(l=0;l<x-k-1;l++)
if(s[l]==j)
f=1;
if(f==1)
{
f=0;
continue;
}
s[x-k-1]=j;
sum(k-1,j,m-j);
}
}
}
int main()
{
int n,k,a,i,j;
scanf("%d,%d",&n,&k);
x=k;
for(i=1;i<n;i++)
{
s=i;
sum(k-2,i,n-i);
}
printf("%d",c);
return 0;
}