I always struggle with calculating time complexities for backtracking problems.
I don't know when it is n! or 2^n. How do you calculate?

I get it where, if the recursive function calls itself k times it's complexity K^N :

• 2 recursive calls - time's complexity is 2^N -
  • https://leetcode.com/problems/remove-invalid-parentheses/discuss/75034/Easiest-9ms-Java-Solution
  • https://leetcode.com/problems/combination-sum/
  • Usually in this approach you either take [one input] into consideration and make a recursive call and then you don't consider it and make another call.
  • This makes the "recursive call tree" look like a binary tree which would have 2^N problems to solve (2^N nodes in that binary tree).
  • So, the time complexity is 2^N.
• 3 recursive calls - time complexity is 3^N - https://leetcode.com/problems/letter-combinations-of-a-phone-number/solution/
  • 3^N just for number with three laters only. I couldnt find a problem wiht exact 3^N complexity.
  • May be, edit distance recursive solution without memoization could be good example for this.
• 4 recursive calls - time complexity is 4^N - https://leetcode.com/problems/expression-add-operators/discuss/71895/Java-Standard-Backtrace-AC-Solutoin-short-and-clear
  • For this though, I think it is 3^N as we are calling it max 3 times in every recursive call. Please let me know if it is still 4^N.

I get iffy when it comes to factorial time complexities.
I will add details on this later as I figure it out. However, if you could help me on this one that would be great!