Leetcode-Combination Series

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