Backtracking [Guide]

#	User	Rating
1	tourist	3880
2	jiangly	3669
3	ecnerwala	3654
4	Benq	3627
5	orzdevinwang	3612
6	Geothermal	3569
6	cnnfls_csy	3569
8	jqdai0815	3532
9	Radewoosh	3522
10	gyh20	3447

#	User	Contrib.
1	awoo	161
2	maomao90	160
3	adamant	157
4	maroonrk	154
5	-is-this-fft-	148
5	SecondThread	148
7	Petr	147
7	atcoder_official	147
9	TheScrasse	145
9	nor	145

Backtracking: This algorithm helps you solve problems in a specific way using your skills in recursive programming. It comes in handy whenever you have a set of valid answers to a problem and need to search through them all or construct a suitable answer, this algorithm is a general algorithm for finding all or some solutions in some computational problems. The backtracking method is an algorithmic method to solve some kind of problems in which we need to build and examine all possible situations or a number of good situations of an arrangement(combination), in this algorithm all possible situations are created , and after examining each one, if it is approved based on the request of the problem we will accept it as a answer(kind of like brute force we find each possible combination). Note that this method is useful when we cant use a faster algorithm(like: Greedy or Dp).

the General Backtracking Method is like this(pseudocode):

solve(X):
if X is accepted:
   X is answer
   exit
while we can change X:
   change X
   if X is valid:
      solve(X)
   undo last change from X

The base of the algorithm is in 4 parts: the condition of finding the answer (lines 1 to 3) — finding all the different states of the answer (lines 4 to 6) — recursive call (line 7) — return the last change made (line 8).

Some Backtracking Problems:

1-Print all strings of length n that are made only of letters a, b, and c.

The Answer

Backtracking method: We perform the same general method, we add one of the letters to the string each round and print it when the length of the string is equal to n, and until the length of the string is less than is n, we repeat this process (if the length of the string is greater than n, we backtrack), code in C++

vector<char> temp;
void print(){
   for (int i = 0; i < n; i++) cout << temp[i];
   cout << ‘\n’;
}
void solve(int i){
   if (i == n) print();
   else if (i > n) return;
   else {
      char chr[3] = {‘a’ , ‘b’ , ‘c’};
      for (int j = 0; j < 3; j++){
         //changing
         temp.push_back(chr[j]);
         //recursive call
         solve(i+1);
         //undo last change
         temp.pop_back();
      }
   }
}

2-A horse is in the cell (0,0) in a n*n chessboard. That is, in the upper-left corner, you have to say the number of cells that the horse can reach with exactly k moves.

The Answer

Backtracking method: we move till, when the number of moves is equal to k, if a new cells found, we add it to our answers (because we may reach the same cells with two different methods). otherwise, if the moves made were more than k, we go back (we backtrack), and if it was less than k, we move the 8 possible moves of the horse and with the condition that after the move we stay inside the chess board, we do each movement again and... , code in C++(result is saved in ans variable)

int ans;
vector<int> answers;
bool inside(int x , int y){
   return x >= 0 && x < n && y >= 0 && y < n;
}
void solve(int x , int y , int i){
   if(i == k && !count(answers.begin() , answers.end() , make_pair(x , y)){
      answers.push_back(make_pair(x , y));
      ans++;
      return;
   }else if(i > k) return;
   else{
      //all possible moves by a knight
      int dx[8] = {1 , 2 , -1 , -2 , -1 , -2 , 1 , 2};
      int dy[8] = {2 , -1 , -2 , 1 , 2 , -1 , -2 , 1};
      for(int j = 0 ; j < 8 ; j++){
         int new_x = x + dx[j];
         int new_y = y + dy[j];
         //changing
         if(inside(new_x , new_y)) //checking is valid
            solve(new_x , new_y , i+1); //recursive call
      }
   }
}

3-476B - Dreamoon and WiFi

The Answer

Backtracking method: in the string each time we reach a '?' , first we will turn it into '-' then into '+' (or reversed) , and when there is no more '?' we count, if it is accepted we will increase the good ways.

#include <bits/stdc++.h>
using namespace std;

string s1;
string s2;
double goods= 0;
double all = 0;
 
void backtrack(int i , int res){
	if(s2[i] == '?'){
                //changing
		s2[i] = '-';
                //recursive call
		backtrack(i , res);
		s2[i] = '+';
		backtrack(i , res);
                //undo last change
		s2[i] = '?';	
	}else if(i == s1.length()-1){
		int ans = 0;
		all++;
		for(auto c : s2){
			if(c == '+') ans++;
			else ans--;	
		}
		if(ans == res) goods++;
 
		return;
	}
	if(i >= s1.length()){
		return;
	}
	if(s2[i] == '+'){ 
		backtrack(i+1 , res);
	}
	else if(s2[i] == '-'){
		backtrack(i+1 , res);
	}
	return;
}

int main() {
    ios::sycn_with_studio(false); cin.tie(0); cout.tie(0);
    cin >> s1 >> s2;
    int res = 0;
    for(auto c : s1){
    	if(c == '+') res++;
	else res--;
    }
    backtrack(0 , res);
    cout << setprecision(9) << goods/all;
}

AlRntn's blog