Problem - Class Assignment (Backtracking Section)

#1

Hi tried to solve this problem but I am getting time limit error. The code which I tried :
#include
using namespace std;
void solve(char *temp,int i,int n,int &count)
{
if(i==n)
{
temp[i] = ‘\0’;
//cout<<temp<<endl;
count++;
return;
}
temp[i] = ‘a’;
solve(temp,i+1,n,count);
if(i==0)
{
temp[i] = ‘b’;
solve(temp,i+1,n,count);
}
else if(temp[i-1]!=‘b’)
{
temp[i] = ‘b’;
solve(temp,i+1,n,count);
}
}
int main() {
int t;
cin>>t;
while(t–)
{
int n;
cin>>n;
int count=0;
char temp[n+1];
solve(temp,0,n,count);
cout<<count<<endl;
}
return 0;
}

#2

Hello Gourav,
your backtrack solution is correct

#3

but to pass test case you need to apply any other technique like dynamic programming.I know the problem is in backtrack category but backtrack solution won’t pass.
try to solve it using dynamic programming.
regards
Aman yadav

1 Like