Permutations

Generate all permutations of a list using recursion and backtracking.

recursion backtracking permutations list

Implement the function `permutations(elements)` that takes a list of distinct items and returns a list of all possible permutations (orderings) of those items.

The order of the permutations in the output does not matter. However, each permutation must be a list containing all original elements exactly once. If the input list is empty, return `[[]]`.

Your function should handle inputs where the elements are hashable (e.g., integers, strings). The input list will contain distinct elements, so there will be no duplicate permutations to eliminate.

Use recursion with backtracking. You may add any helper functions inside `permutations` or externally, as long as `permutations` is the entry point.

Constraints

Input length `n` satisfies `0 <= n <= 8`.

All elements in the input are distinct and hashable.

The output size is `n!` (factorial of `n`). Time complexity should be `O(n * n!)` in the worst case, which is inherent to output size.

Example

>>> permutations([1,2,3])
[[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

>>> permutations([])
[[]]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Base case: when the list is empty, return a list containing an empty list.

For each element, remove it from the list and generate permutations of the remaining elements, then prepend that element to each.

Use recursion with a helper that builds permutations incrementally.

If using backtracking, remember to undo the removal/choice after recursion.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.