What is the best time complexity of this problem?


  • 1
    D

    It seems taking exponential time: O(4^n) by DFS solution.

    Does this problem have polynomial time solution?


  • 2
    D

    Mentioned this in another comment: for nums="0000..0", target=0 and you get the output consisting of 3^(n-1) strings.


  • 0
    D

    Thanks for your answer.
    Looks like the actual number of the output is much less than 3^(n-1) except for case:"000..0" only. Does it have solution in polynomial time ?


  • 0
    D

    One can construct other exponential cases, e.g. nums="AdddBddCdddd..dddd" with even number of d's and target=A+B+C. In this case you'll have at least a set of strings where all d's evaluate to 0 and doing this with only '+'s and '-'s between d's will be exponential.

    On the other hand there are special cases that are solvable in O(N). E.g. nums consisting of only even digits and an odd target or if nums consists of 0,3,6,9 and target is not divisible by 3.


Log in to reply
 

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