Programming Template: BackTraking

#programming #cpp #algorithms

This is a simple code example of backtraking. This traverses the problem space in depth-first order. I memorized it as a solution template.

const int MAXC = 4;
int finished = 0;
void bt(int a[], int k, int n) {
    int candidates[MAXC], numCand, i;
    if (solved(a, k, n)) {
        answer(a, k, n);
        return;
    }
    numCand = getCandidates(a, k, n, candidates);
    for (i = 0; i < numCand; i++) {
        a[k] = candidates[i];
        bt(a, k + 1, n);
        if (finished) return;
    }
}