I am writing a recursive function to create all possible subsequences of a string and return the set of strings as a vector. This is a challenge from Coding Ninjas. I recurse over each char in the string and generate two cases, whether I want to keep the character or delete it from the string and when the base case hits, the string generated is added into the ans
vector, which contains all the subsequences. This is how my code looks:
void recurse(string str, string value, int idx, vector<string> &ans){
//base case
if(idx < 0 && !value.empty()){
ans.push_back(value);
return;
}
//keep letter
recurse(str, value, idx-1, ans);
//delete letter
value.erase(idx,1);
recurse(str, value, idx-1, ans);
}
vector<string> subsequences(string str){
vector<string> ans;
string value = str;
recurse(str, value, str.size()-1, ans);
return ans;
}
This gives a runtime error on the if condition in recurse function: if(idx < 0 && !value.empty())
.
But if I create a separate if statement to check for the !value.empty()
condition, it runs perfectly fine and the solution is correct. The correct code block without runtime error is this:
//base case
if(idx < 0){
if(!value.empty()) ans.push_back(value);
return;
}
The condition is necessary so that the last empty string is not added to the ans
vector. Can anyone explain why when checking for 2 conditions together using &&
gives a runtime error but when checking for them separately with a nested if block, it runs completely fine?
The two conditions
if(idx < 0 && !value.empty())
and
if(idx < 0){
if(!value.empty())
are not equivalent.
If idx < 0
is true but !value.empty()
is false, then in the first variant (with the &&
operator) will be false and you will recurse again.
With the second variant it doesn't matter what result you get from !value.empty()
. The function will still return
and not recurse.
That means the first alternative will recurse far longer and deeper, perhaps too deep for the call stack to be able to handle.
It might be easier to understand the difference if we rewrite the code slightly...
The first, with if(idx < 0 && !value.empty())
is equivalent to:
if (idx < 0)
{
if (!value.empty())
{
ans.push_back(value);
return;
}
}
The second is equivalent to:
if (idx < 0)
{
if (!value.empty())
{
ans.push_back(value);
}
return;
}
Note the location of the return
statement.