Simple C++ Soln using backtracking


#1

void getmax(string A, int B, string& m){
if(B==0)
return;
for(int i=0;i<A.size()-1;i++)
for(int j=i+1;j<A.size();j++){
if(A[j]>A[i]){
swap(A[j], A[i]);
if(A>m)
m = A;
getmax(A, B-1, m);
swap(A[j], A[i]);
}
}
}

string Solution::solve(string A, int B) {
string m = A;
getmax(A, B, m);
return m;
}


#2

Can you please explain a little bit what and why are you doing like this and why this is working for larger test cases and not iterative approach.


#3

Why is swap statement present after the recursive call to getmax() ?


#4

Hi Inception, swap statement is there to return back to the older state and then continue.


#5

Why do we need to get back to original state. We aren’t returning A[], right ? I realized that not returning to older state breaks the code, but I did not understand why ?


#6

To maintain the string A that came into the function. he could have also gotten the string A as reference. could have saved copying of string A in each recursive call.


#7

Becoz there can be certain swaps in A string which could be more beneficial than others.
for A = 235, B = 1… first swap will be 325 (3 and 2) but more better could be 532.(5 and 2) for this we need to know the original array(235) and not the transformed array(325).