Learn and practice the Backtracking and Subsets patterns to solve coding interview problems.

Educative-99 in JavaScript: Accelerate Your Coding Interview Prep

The optimal solution to certain problems requires examining all possibilities. If any possibility is ignored, we are unable to say with mathematical certainty that our solution is optimal. In such situations, we use a technique known as backtracking to exhaustively traverse the entire solution space and collect all the information needed to compute the optimal solution. The Subsets pattern groups together those problems where we need to systematically construct all, or, a mathematically defined subset of all, the possible subsets of a given set. Again, the technique used for the construction of such a set of subsets is, in fact, backtracking.

Go With the Flow

# Statement

Given an input string, `word`, return all possible permutations of the string.

> **Note:** The order of permutations does not matter. 

**Constraints:**

* All characters in `word` are unique.

* $1 \leq$ `word.length` $\leq 6$
* All characters in `word` are lowercase English letters.

# Pattern: Subsets

Problems such as this one, where we need to find the combinations or permutations of a given string, are good examples to solve using the subsets pattern as it describes an efficient **Depth-First Search (DFS)** approach to handle all these problems.

# Solution

Let's discuss a few basics first. We know that $n!$ is the number of permutations for a set of size $n$. Another obvious and important concept is that if we choose an element for the first position, then the total permutations of the remaining elements are $(n-1)!$.

For example, if we’re given the string “abcd” and we pick “a” as our first element, then for the remaining elements we have the following permutations:

Let's solve the Permutations problem using the Subsets pattern.

Backtracking

Subsets

Conclusion