DSA problem
Permutations
Given an array nums of n distinct integers, return all possible permutations of those integers. Each permutation is an ordering of all n values, and the answer set has exactly n! entries.
This is the canonical "fix the prefix, recurse on the suffix" backtracking problem. At each level of the recursion we decide which previously unused element to place next in the current arrangement. With n distinct numbers there are n choices at depth 0, n - 1 at depth 1, and so on, multiplying out to n! total leaves.
A clean way to implement this is to maintain a boolean used[] array of length n alongside a growing path. We iterate over the indices: whenever used[i] is false, we mark it true, push nums[i] onto path, recurse, and then un-mark the choice (the classic "choose / recurse / un-choose" pattern that gives backtracking its name).
When path.length == n we have a complete permutation, so we snapshot a copy into the results — copying is critical because path is mutated as the recursion unwinds. Time complexity is O(n * n!) (we generate n! permutations and each costs O(n) to copy) and space is O(n) for the recursion stack and used[] arrays, not counting the output.
Examples
nums = [1,2,3][[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]nums = [0,1][[0,1],[1,0]]nums = [1][[1]]Constraints
- 1 <= nums.length <= 6
- -10 <= nums[i] <= 10
- All the integers of nums are unique.
- The output may be returned in any order.
- Each returned permutation must contain every element exactly once.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.