hi can someone tell me why bool function is returning false

I am writing a function canConstruct() that will take targeSum and a List of strings containing substrings. The function should return a boolean indicating wheather or not the targetSum can be constructed by concatenating elements of the list.

you may reuse the elements of the list as many times as needed.

my solution:

List abb = new List();
//abb.Add("ab");
abb.Add("abc");
//abb.Add("de");
abb.Add("def");
abb.Add("cdef");
string target = "abcdef";
Console.WriteLine(canConstruct(target,abb));

bool canConstruct(string targetSum, List arrayofstring )
{

if (string.IsNullOrEmpty(targetSum))
{

return true;

}
foreach (var rr in arrayofstring)
{
if (targetSum.IndexOf(rr) == 0 && rr.Length<=targetSum.Length)
{
string new_rr = targetSum.Remove(0, rr.Length);
canConstruct(new_rr, arrayofstring);
}

}

return false;
}

but the problem here is my solution is returning false, despite returning true in one of the callstacks the overall answer is false, also the program is not exiting after true is returned from callstack , can someone pls help.

1 Reply

Know the answer? Post it — somebody with the same question will find it here.

Muhammad Imran Ansari4y ago
Accepted answer
You program is running recursively and due to callstack behaviour complete all the stack enteries and retun overall answer. You need to modify your code to break callstack enteries like:
bool canConstruct(string targetSum, List<string> arrayofstring)
{
    bool returnVal = false;

    foreach (var rr in arrayofstring)
    {
        if (string.IsNullOrEmpty(targetSum))
        {
            returnVal = true;
            break;
        }
        if (targetSum.IndexOf(rr) == 0 && rr.Length <= targetSum.Length)
        {
            string new_rr = targetSum.Remove(0, rr.Length);
            canConstruct(new_rr, arrayofstring);
        }
    }
    return returnVal;
}
0