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.

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.

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 ...