[UVa] 729 - The Hamming Distance Problem

Method: Bruteforce, all combinations. Permutation. Backtracking.
Trick: Finding all the results is pretty easy using any Basic Backtracking code but you have to sort them. So? Don't work with 1s work with 0s. Or just use next_permutation( ) from STL, your choice. Optimizations: Pregenerating all combinations might give you a better runtime, didn't try it.

Sample Input:

1

16 7

Sample Output:

Please find it using UVA Toolkit (www.uvatoolkit.com)

/* Faith-M */

//Headers
#include <set>
#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <climits>
#include <clocale>
//Defines
#define pow2(i) (1<<i)
#define bit(i) (1<<i)
#define isOdd(i) (i&1)
#define isEven(i) (!(i&1))
#define isPrime(i) ((i==2) || ((i&1) && !pTest[i])) //pTest has to be the bool array's name
#define sz(i) i.size()
#define vec(type,name) vector< type > name
#define rep(i,a,b) for(int i=a ; i<=b ; i++)
#define swap(type,a,b) {type t=a; a=b; b=t;}
#define sum(a,n) ( (n*(n+1)/2) - (a-1)*a/2 )
#define iscap(i) (i>='A'&&i<='Z')
#define issmall(i) (i>='a'&&i<='z')
#define isnum(i) (i>='0'&&i<='9')
#define issymbol(i) (!(i>='a'&&i<='z') && !(i>='A'&&i<='Z') && !(i>='0'&&i<='9'))
#define mk(i,j) make_pair(i,j)
#define ERROR 1e-11
//Type Defs
typedef long long lint;
typedef unsigned long long ulint;
typedef long double ldouble;

using namespace std;

int st[20];

void func(int n, int h, int cnt, int x)
{

    if (cnt >= h)
    {
        for (int j=1 ; j<=n ; j++)
        {
            printf("%d",st[j]);
        }
        printf("\n");


        return;
    }

    for (int i=x ; i<=n ; i++)
    {
        if (st[i] == 1)
        {
            st[i] = 0;

            func(n,h,cnt+1,i+1);

            st[i] = 1;
        }
    }

    return;
}

int main()
{
    //freopen("input.txt","r+",stdin);
    //freopen("output.txt","w+",stdout);/**/

    //    TEST CASE     //
    int kase=1, kounter=1;/**/

    int n, h;

    bool blnk = false;

    scanf("%d",&kase);

    while ( kase-- )
    {
        if (blnk) printf("\n");
        else blnk = true;

        for (int i=1 ; i<=20 ; i++)
        {
            st[i] = 1;
        }

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

        func(n,n-h,0,1);
    }


    return 0;
}