is the time complexity 3^N and space complexity 3^N???


  • 0
    T

    is the time complexity 3^N and space complexity 3^N???


  • 0

    Assuming you used dfs, the time complexity is 3^(N-1) (N-1 because there is no branching for the first element) where N is the length of the string because for every instance of recursion you have 3 branches, (+,-,*). for example, with "123". at 1 you will produce 3 branches 1+2,1-2,1*2 and for each of these branches you will get 3 more branches and so on.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.