runtah

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(" ");
 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;
}

Go to link download