[UVa] 574 - Sum It Up

Method: Backtracking
Possible optimizations: Used a map to check if a set was generated before, it takes more time than checking if the numbers were used more than they appeared in input

#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
using namespace std;

vector<int> nlist;
vector< vector<int> > finlist;
bool used[20];
map< vector<int>, bool > mp;
int btracking(int t, int sum, vector<int> temp, int k) {
    //if (!sum) solve[i].clear();

    if (sum == t) {
        if (!mp[temp]) {
            finlist.push_back(temp);
            mp[temp] = true;
        }
        return 0;
    }

    for (k ; k<nlist.size() ; k++) {
        if (!used[k]) {
            if (nlist[k]<=(t-sum)) {
                sum+=nlist[k];
                temp.push_back(nlist[k]);
                used[k] = true;
                btracking(t, sum, temp, k);
                used[k] = false;
                temp.pop_back();
                sum-=nlist[k];
            }
        }
    }

    return 0;
}

int main( void ) {

    int t, n, i, j, x;

    //freopen("574_in.txt","r+",stdin);

    while ( scanf("%d %d",&t,&n) == 2 ) {
        if (!n) break;

        printf("Sums of %d:\n",t);

        nlist.clear();
        for (i=0 ; i<n ; i++) {
            scanf("%d",&x);
            nlist.push_back(x);
            used[i] = false;
        }
        //cout << "-----> " << nlist.size() << endl;

        finlist.clear();
        vector<int> temp;
        temp.clear();
        mp.clear();
        btracking(t, 0, temp, 0);

        if (!finlist.size()) {
            printf("NONE\n");
        }

        //printf("--> %d\n",finlist.size());
        for (i=0 ; i<finlist.size() ; i++) {
            for (j=0 ; j<finlist[i].size() ; j++) {
                if (!j) printf("%d",finlist[i][j]);
                else printf("+%d",finlist[i][j]);
            }
            printf("\n");
        }

    }

    return 0;
}

Backtracking Basic Code

This is one of the first things you do when you learn how to program a backtracking simulation. Generate all permutations of a given number range. When the program is at halt enter any number greater than 0 to see all numbers in that range permuted. The program terminates with the 0 input.

#include <cstdio>
#include <iostream>
using namespace std;

int src[100], out[100], used[100], n;

void btrack( int k ) {
 
 if (k>=n) {
  for (int i=0 ; i<n ; i++) {
   printf(" %d ",out[i]);
  }
  printf("\n");
  return;
 }
 
 for (int i=0 ; i<n ; i++) {
  if (!used[i]) {
   used[i] = 1;
   out[k] = src[i];
   btrack( k+1 );
   used[i] = 0;
  }
 }
 return;
}


int main ( void ) {
 
 while ( scanf("%d",&n) && n ) {
  for (int i=0 ; i<n ; i++) {
   used[i] = 0;
   src[i] = i+1;
  }
  btrack( 0 );
 }
 
 return 0;
}

[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;
}

[UVa] 167 - The Sultan's Successors

One thing's for sure, Backtracking is damn fun!!! :D
I liked this one a lot. Though I had to take some help for this one. But it still increased a lot of knowledge about Backtracking.

#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;

bool col[100], d1[100], d2[100];

class c
{
    public:
    int x, y;
};

c crd[100];

int knt=0, board[100][100];

c lst[1000];

int qplace(int n)
{
    if (n>8)
    {
        for (int i=1 ; i<=8 ; i++)
        {
            lst[knt++]=crd[i];
        }
        return 0;
    }
    for (int k=1 ; k<=8 ; k++)
    {
        if (!col[k] && !d1[n+k] && !d2[n-k+8])
        {
            col[k]=d1[n+k]=d2[n-k+8]=true;
            crd[n].x = n;
            crd[n].y = k;
            qplace(n+1);
            col[k]=d1[n+k]=d2[n-k+8]=false;
        }
    }
    return 0;
}

int main()
{
    int test, i, j, sum, max;
    knt = 0;
    for (i=0 ; i<=100 ; i++)
        col[i]=d1[i]=d2[i]=false;
    qplace(1);
    //cout << knt << endl;



    scanf("%d",&test);
    while (test--)
    {
        for (i=1 ; i<=8 ; i++)
        {
            for (j=1 ; j<=8 ; j++)
            {
                scanf("%d",&board[i][j]);
            }
        }
        max = 0;
        for (i=0 ; i<knt ; i+=8)
        {
            for (j=i, sum=0 ; (j-i)<8 ; j++)
            {
                sum += board[lst[j].x][lst[j].y];
            }
            if (sum>max)
                max = sum;
        }
        cout << setw(5) << max << endl;
    }
    return 0;
}