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. 😉😃💗