Backtracking: Letter case permutation

You are given a string, you need to transform every letter individually to be lowercase or uppercase to create another string.

Input: “a1b”

Output: “a1b”, “A1b”, “a1B”, “A1B”

We can solve this problem by using DFS method.

Explanations is as below:

        a1b2   i=0 = a, as it is a letter, we have two branches: a, A
     /        \
   a1b2       A1b2 i=1 = 1, we only have 1 branch that is itself
    |          |   
   a1b2       A1b2 i=2 = b, we have two branches: b, B
   /  \        / \
  a1b2 a1B2  A1b2 A1B2 i=3 = S.length(), we end the recursion here.

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<vector>
#include<set>

using namespace std;

void backtrace( string S, int i, vector<string> &result ) 
{
  if( i == S.length() ) 
  {
      result.push_back( S );
      return; 
  } 
  
  if( 'a' <= S[i] && S[i] <= 'z' ) 
  { 
      backtrace( S, i + 1, result );
      S[i] = 'A' + S[i] - 'a';
      backtrace( S, i + 1, result );
  } else if ( 'A' <= S[i] && S[i] <= 'Z' ) { 
      backtrace( S, i + 1, result );
      S[i] = 'a' + S[i] - 'A';
      backtrace( S, i + 1, result );
  } else { 
      backtrace( S, i + 1, result );
  }
  
}
vector<string> letter_case_permutation( string S ) 
{
  vector<string> result;
  backtrace( S, 0, result );
  return result;
}



int main()
{

   vector<string> result = letter_case_permutation("a1b");
   cout<<"Result = "<<endl;
   for (int i = 0; i < result.size(); i++)
    {
      cout<<result[i]<<" ";
    }


    return 0;
}

/*
   vector<vector<int> > result = combine(n, k);
   cout<<"Result = "<<endl;
   for (int i = 0; i < result.size(); i++)
    {
        for (int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j] << " ";
        }   
        cout << endl;
    }
    */

Output:

Result =
a1b a1B A1b A1B