Generate all permutations of an array
Company: SoFi
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Given an array `nums` of **distinct** integers, return **all possible permutations** of the array.
A permutation is an ordering of all elements in the array, and each element must appear **exactly once** in each permutation.
## Input
- `nums`: an array of integers with no duplicates.
## Output
- A list of permutations, where each permutation is a list/array of integers.
- You may return the permutations in **any order**.
## Constraints
- `1 <= nums.length <= 10`
- `-10 <= nums[i] <= 10`
- All values in `nums` are unique.
## Example
**Input:** `nums = [1,2,3]`
**Output (one valid ordering):**
```
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
```
## Notes
- Aim for a solution using DFS/backtracking.
- Consider how to track which elements have been used in the current partial permutation.
Quick Answer: This question evaluates understanding of permutation generation, recursion and backtracking techniques, along with skills in state-space exploration and analysis of time and space complexity.
Given an array `nums` of distinct integers, return all possible permutations of the array. A permutation is an ordering of all elements where each element appears exactly once. You may return the permutations in any order, but the reference solution generates them using DFS/backtracking by trying numbers from left to right.
Constraints
- 1 <= len(nums) <= 10
- -10 <= nums[i] <= 10
- All values in nums are unique
Examples
Input: ([1, 2, 3],)
Expected Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Explanation: There are 3! = 6 permutations of [1, 2, 3].
Input: ([0],)
Expected Output: [[0]]
Explanation: A single-element array has exactly one permutation: itself.
Input: ([-1, 2],)
Expected Output: [[-1, 2], [2, -1]]
Explanation: A 2-element array has 2 permutations, including when values are negative.
Hints
- Build the permutation one position at a time using recursion.
- Keep track of which indices have already been used in the current permutation so you do not reuse an element.