By Long Luo

Here shows 2 Approaches to slove this problem: Backtracking and Bit Mask.

# Backtracking

A very easy backtracking solution. Just refer to 17. Letter Combinations of a Phone Number.

## Analysis

• Time Complexity: $O({M \choose k} \times k)$, $M$ is the size of combinations, $M = 9$, the total combinations is $M \choose k$.
• Space Complexity: $O(M + k)$, size of $path$ is $k$, the recursion stack is $O(M)$.

Since the numbers are just from $1$ to $9$, the total sum of combinations is $2^9=512$.

We can map $1$ - $9$ with a number with a length of 9-bits number, bits $0$ means selecting $1$, bits $8$ means selecting $9$.

Eg:

$000000001b$, means [1]
$000000011b$, means [1,2]
$100000011b$, means [1,2,9]

We can search from $1$ to $512$, take the number corresponding to the bit value of $1$ in $i$, and sum it up to see if it is satisfied.

## Analysis

• Time Complexity: $O(M \times 2^M)$, $M = 9$, every state needs $O(M + k) = O(M)$ to check.
• Space Complexity: $O(M)$, $M$ is size of $\textit{path}$.

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗