# 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