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

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

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