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

Using recursion + cache for time complexity analysis typically follows the pattern:

1. Maximum Number of States in Cache:Identify the maximum number of states your cache can hold. In the example of Word Break, which is a 1D DP problem, it can have up to n states.
2. Number of Paths for Each Node in Decision Tree: Determine the number of paths for each node in the decision tree. In Word Break, it’s m paths.
3. Operation at Each Node: the operation performed at each node. In 139. Word Break, the operation is string matching, which takes O(k) operations.

Taking 139. Word Break as an example:

• Maximum number of states in cache (n).
• Each node in the decision tree has m paths.
• Each node performs a string matching operation, taking O(k) operations.

Therefore, the total time complexity is O(n * m * k).

In other problems, if the exploration paths are constant, and each node operation is O(1), the time complexity can be simplified to O(n).