Q729: The Hamming Distance Problem

//  Run time: 0.820
#include <stdio.h>
#define N 16
int arr[N];
int len, distance;
void test(int len);
void calculate();
void print();

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

    while (n--)
    {
        scanf("%d%d", &len, &distance);
        test(len);
        if (n)
            printf("\n");
    }

    return 0;
}

void test(int len)
{
    int i, j;
    int prod = 1;
    for ( i = 0; i < len; i++)
    {
        arr[i] = 0;
        prod *= 2;
    }

    for ( i = 0; i < prod; i++)
    {
        calculate();
        arr[0]++;
        for ( j = 0; j < len-1; j++)
        {

            if (arr[j] >= 2)
            {
                arr[j+1] += arr[j]/2;
                arr[j] %= 2;
            }
        }
    }
}

void calculate()
{
    int i;
    int count = 0;
    for ( i = 0; i < len; i++)
        count = arr[i] ? count+1 : count;

    if (count == distance)
        print();
}

void print()
{
    int i;
    for ( i = len-1; i >= 0; i--)
        printf("%d", arr[i]);
    printf("\n");
}