The optimal solution runs in O(n*2^n) time and O(2^n) space.

The recommended approach seems to have a branching factor of four and a branching depth of n, meaning a time complexity of O(4^n) and space complexity of O(n). Am I interpreting that correctly? If so, is the optimal solution different from the recommended one?

Course: Grokking Coding Interview Patterns in Python - Learn Interactively

Lesson: Matchsticks to Square - Grokking Coding Interview Patterns in Python