Generate All Permutations

Write a function generatePermutations that finds all the of an input string.

If there are duplicate letters, you should include the duplicate permutations of each.
Time and space complexity is not considered for the quality of the solution — focus on readable code.

Interactive Permutation Animation

Breakdown

Approach and test strategy

Backtracking with explicit multiplicity and an empty permutation

Read the approach, boundary cases, and complexity

Build arrangements by choosing one remaining position at each step, exploring its suffix, and undoing the choice before trying the next position. This lesson retains repeated permutations when repeated letters occupy different chosen positions. Deduplicating the result would change the required multiplicity. The empty string has one permutation, itself, because one completed arrangement remains when there are no positions left to choose.

Cases to check

The empty string returns a collection containing one empty string.
For two distinct letters, check both arrangements.
Include repeated letters and compare result multiplicities, not just a set of unique strings.

Cost model

Materializing all n! positional arrangements of length n takes at least O(n · n!) character output work. Working path state can be linear; retained output is much larger.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

Follow teacher

Table of Contents

Validate My Answer

Our constraint says that the Big O complexity should not be factored into picking a solution. You will likely want to use recursion because the iterative solution is painfully long.
Duplicate strings are allowed in the result if they form the same permutation. You only need to focus on creating the logic for the permutations without needing to validate.
Any recursive solution must have a base case. Think through what it would be here and ensure it's included in your solution.

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {str} string
 * @return {List[str]}
 */
const generatePermutations = (string) => {
  // Your solution here
};

Generate All Permutations

Write a function generatePermutations that finds all the of an input string.

If there are duplicate letters, you should include the duplicate permutations of each.
Time and space complexity is not considered for the quality of the solution — focus on readable code.

/**
 * @param {str} string
 * @return {List[str]}
 */
const generatePermutations = (string) => {
  // Your solution here
};