AOJ 0030 Sum of Integers

Sum of Integers

Write a program which reads n digits chosen from 0 to 9 and prints the number of combinations where the sum of the digits equals s. You can not use the same digits in a combination. For example, the combinations where n = 3 and s = 6 are as follows:

1 + 2 + 3 = 6
0 + 1 + 5 = 6
0 + 2 + 4 = 6
Input

The input consists of several datasets. Each dataset includes n and s separated by a space.

The input ends with a case where n = 0 and s = 0.

Output

For each dataset, print the number of combination in a line.

Sample Input

3 6
3 1
0 0
Output for the Sample Input

3
0

#include <iostream>
using namespace std;

int numofbits5(long bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main(){
int n,s,ret,sum;
while(cin >> n >> s && n || s){
ret = 0;
for(int i=0;i < (1<<10);i++){

   if(numofbits5(i) != n)continue;
   cout<<i<<endl;
   sum = 0;// cout<<i<<" "<<numofbits5(i)<<" "<<n<<endl;
   for(int j=0;j<10;j++){
     if( (1<<j)&i){sum += j;cout<<( (1<<j)&i)<<" "<<j<<endl;}
   }
   cout<<endl;
   if(sum == s)ret++;
}
cout << ret << endl<<endl;
}
}