Permutations

Difficulty: Hard · Topic: Recursion

Given a list of distinct integers nums, return all possible permutations (in any order). Build each permutation by choosing an unused element at every depth and undoing the choice on the way back up.

Examples

permute([1,2,3])
→ [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

permute([0,1])
→ [[0,1],[1,0]]

permute([1])
→ [[1]]

Target complexity: time O(n · n!), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.