Usually, when it comes to combination problems, the most naive way to solve the problem is generate all possible solutions. And, we use depth-first-search(DFS) or called backtracking technique.
For backtracking, when we do time and space complexity analysis, they follow a certain pattern:
T: O(n**m), n raise to power of m, where n represents at most we have n branches can search for current state and m is maximum depth of recursion tree.
Note: O(n**m) will be upper bound of time complexity. For some cases, if we generate all possible combinations or partitions , given an integer or a string, running time will be O(2**n), lower than upper bound.
S:O(m), where m is maximum depth of recursion tree. (if we don’t consider space of storing answer)
- 39. Combination Sum
- 131. Palindrome Partitioning
- 291. Word Pattern II