# Permutations
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/permutations)
Canonical: https://scaleengineer.com/dsa/problems/permutations
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [American Express](https://scaleengineer.com/companies/american-express), [Apple](https://scaleengineer.com/companies/apple), [Barclays](https://scaleengineer.com/companies/barclays), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Cisco](https://scaleengineer.com/companies/cisco), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [LinkedIn](https://scaleengineer.com/companies/linkedin), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [Qualcomm](https://scaleengineer.com/companies/qualcomm), [ServiceNow](https://scaleengineer.com/companies/servicenow), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [Zoho](https://scaleengineer.com/companies/zoho), [eBay](https://scaleengineer.com/companies/ebay), [Citadel](https://scaleengineer.com/companies/citadel), [Microstrategy](https://scaleengineer.com/companies/microstrategy), [Booking.com](https://scaleengineer.com/companies/booking.com), [Workday](https://scaleengineer.com/companies/workday)
---
## Problem
Given an array `nums` of distinct integers, return all the possible permutations. You can return the answer in **any order**.

**Example 1:**

**Input:** nums = [1,2,3]
**Output:** [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

**Example 2:**

**Input:** nums = [0,1]
**Output:** [[0,1],[1,0]]

**Example 3:**

**Input:** nums = [1]
**Output:** [[1]]

**Constraints:**

* `1 <= nums.length <= 6`
* `-10 <= nums[i] <= 10`
* All the integers of `nums` are **unique**.

# Approaches
## Backtracking with a `used` Array
This approach uses a classic backtracking algorithm. We build a permutation step-by-step using a recursive helper function. To avoid using the same element multiple times in a single permutation, we maintain a boolean `used` array.
**Time:** O(N * N!) · **Space:** O(N)
**Pros:** Conceptually straightforward and a very common pattern for solving permutation, combination, and subset problems.; Easy to understand and implement.
**Cons:** Requires extra space for the `used` array to keep track of which elements have been included in the current permutation.
### Explanation
The core of this solution is a recursive function, let's call it `backtrack`. This function is responsible for building permutations. We pass it the list of results, the current permutation being built, the original numbers, and a `used` array.

The base case for the recursion is when the size of the current permutation equals the size of the input `nums` array. This signifies that a complete, valid permutation has been formed. We then add a copy of this permutation to our final result list and return from that recursive call.

In the recursive step, we loop through all the numbers in the input array. For each number, we check our `used` array to see if it has already been included in the current permutation. If it hasn't, we add it to our current permutation, mark it as used, and then make a recursive call to continue building the permutation from this new state. 

Once the recursive call returns, we must "backtrack". This is a critical step where we undo the choice we just made so that we can explore other possibilities. We remove the number we just added from the current permutation and update its status in the `used` array back to `false`. This allows that number to be picked at a different position in a future permutation.

```java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        boolean[] used = new boolean[nums.length];
        backtrack(result, new ArrayList<>(), nums, used);
        return result;
    }

    private void backtrack(List<List<Integer>> result, List<Integer> currentPermutation, int[] nums, boolean[] used) {
        if (currentPermutation.size() == nums.length) {
            result.add(new ArrayList<>(currentPermutation));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (!used[i]) {
                currentPermutation.add(nums[i]);
                used[i] = true;
                backtrack(result, currentPermutation, nums, used);
                // Backtrack
                used[i] = false;
                currentPermutation.remove(currentPermutation.size() - 1);
            }
        }
    }
}
```
### Algorithm
1. Initialize an empty list `result` to store all permutations.
2. Initialize a boolean array `used` of the same size as `nums`, with all values set to `false`.
3. Define a recursive function `backtrack(currentPermutation)`:
    a. **Base Case:** If `currentPermutation.size()` is equal to `nums.length`, it means we have formed a complete permutation. Add a copy of `currentPermutation` to `result` and return.
    b. **Recursive Step:** Iterate through each number in the `nums` array from index `i = 0` to `nums.length - 1`.
        i. If the number at index `i` has not been used yet (`used[i]` is `false`):
            - Add `nums[i]` to `currentPermutation`.
            - Mark it as used by setting `used[i]` to `true`.
            - Make a recursive call: `backtrack(currentPermutation)`.
            - **Backtrack:** After the recursive call returns, undo the choice. Set `used[i]` back to `false` and remove the last element from `currentPermutation`.
4. Start the process by making an initial call to `backtrack` with an empty list.
5. Return the `result` list.

## Backtracking with In-place Swaps
This is a more space-efficient backtracking approach. Instead of using an auxiliary `used` array to track which elements have been used, we generate permutations by performing in-place swaps within the input array itself. The key idea is to fix an element at a certain position and then recursively generate all permutations for the remaining part of the array.
**Time:** O(N * N!) · **Space:** O(N)
**Pros:** More space-efficient as it avoids the O(N) space required for a `used` array or set.; It's an elegant in-place solution that demonstrates a powerful backtracking technique.
**Cons:** The concept of in-place swapping and backtracking might be slightly less intuitive at first compared to using a `used` flag.; This method modifies the array passed into the recursive function. If the original input array needs to be preserved, a copy should be made before starting the process.
### Explanation
The algorithm works by defining a portion of the array that is 'fixed' and a portion that we can still permute. A recursive function, say `backtrack(first, nums)`, is used, where `first` is the index of the first element in the portion of the array we are currently considering for permutation.

The base case is when `first` reaches the end of the array (`first == nums.length`). This implies that all positions have been filled, and the current arrangement of `nums` is a complete permutation. We convert the array to a list and add it to our results.

In the recursive step, we iterate from the `first` index to the end of the array. For each index `i` in this range, we swap the element `nums[i]` with `nums[first]`. This action effectively places `nums[i]` as the first element of the subarray we are permuting. After the swap, we make a recursive call `backtrack(first + 1, nums)` to generate all permutations for the rest of the array (from `first + 1` onwards). 

After the recursive call returns, we must backtrack by swapping `nums[i]` and `nums[first]` again. This undoes the previous swap, restoring the array to its state before the choice was made. This allows us to explore placing a different element at the `first` position in the next iteration of the loop.

```java
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(0, nums, result);
        return result;
    }

    private void backtrack(int first, int[] nums, List<List<Integer>> result) {
        if (first == nums.length) {
            List<Integer> permutation = new ArrayList<>();
            for (int num : nums) {
                permutation.add(num);
            }
            result.add(permutation);
            return;
        }

        for (int i = first; i < nums.length; i++) {
            // Place i-th integer first in the current permutation
            swap(nums, first, i);
            // Use next integers to complete the permutations
            backtrack(first + 1, nums, result);
            // Backtrack
            swap(nums, first, i);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
```
### Algorithm
1. Initialize an empty list `result` to store all permutations.
2. Define a recursive function `backtrack(first, nums)` where `first` is the index of the element we are trying to place.
3. **Base Case:** If `first` is equal to `nums.length`, it means all elements have been placed. Convert the current state of the `nums` array to a list and add it to `result`. Then return.
4. **Recursive Step:** Iterate from `i = first` to `nums.length - 1`.
    a. Swap the element at index `first` with the element at index `i`. This places the `i`-th element into the `first` position.
    b. Make a recursive call: `backtrack(first + 1, nums)` to generate permutations for the rest of the array.
    c. **Backtrack:** Swap the elements at `first` and `i` back to their original positions. This is crucial to restore the array for the next iteration of the loop.
5. Start the process by calling `backtrack(0, nums)`.
6. Return `result`.

# Solutions
### CSharp

```csharp
public class Solution {
    public IList < IList < int >> Permute(int[] nums) {
        var ans = new List < IList < int >> ();
        var t = new List < int > ();
        var vis = new bool[nums.Length];
        dfs(nums, 0, t, vis, ans);
        return ans;
    }
    private void dfs(int[] nums, int i, IList < int > t, bool[] vis, IList < IList < int >> ans) {
        if (i >= nums.Length) {
            ans.Add(new List < int > (t));
            return;
        }
        for (int j = 0; j < nums.Length; ++j) {
            if (!vis[j]) {
                vis[j] = true;
                t.Add(nums[j]);
                dfs(nums, i + 1, t, vis, ans);
                t.RemoveAt(t.Count - 1);
                vis[j] = false;
            }
        }
    }
}
```

### Java

```java
class Solution { private List < List < Integer >> ans = new ArrayList <>(); private List < Integer > t = new ArrayList <>(); private boolean [] vis ; private int [] nums ; public List < List < Integer >> permute ( int [] nums ) { this . nums = nums ; vis = new boolean [ nums . length ]; dfs ( 0 ); return ans ; } private void dfs ( int i ) { if ( i == nums . length ) { ans . add ( new ArrayList <>( t )); return ; } for ( int j = 0 ; j < nums . length ; ++ j ) { if (! vis [ j ]) { vis [ j ] = true ; t . add ( nums [ j ]); dfs ( i + 1 ); t . remove ( t . size () - 1 ); vis [ j ] = false ; } } } }
```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number[][]} */ var permute = function (
  nums,
) {
  const n = nums.length;
  const ans = [];
  const t = [];
  const vis = new Array(n).fill(false);
  function dfs(i) {
    if (i >= n) {
      ans.push([...t]);
      return;
    }
    for (let j = 0; j < n; ++j) {
      if (!vis[j]) {
        vis[j] = true;
        t.push(nums[j]);
        dfs(i + 1);
        vis[j] = false;
        t.pop();
      }
    }
  }
  dfs(0);
  return ans;
};

```

### CPP

```cpp
class Solution {
public:
  vector<vector<int>> permute(vector<int> &nums) {
    int n = nums.size();
    vector<vector<int>> ans;
    vector<int> t(n);
    vector<bool> vis(n);
    function<void(int)> dfs = [&](int i) {
      if (i == n) {
        ans.emplace_back(t);
        return;
      }
      for (int j = 0; j < n; ++j) {
        if (!vis[j]) {
          vis[j] = true;
          t[i] = nums[j];
          dfs(i + 1);
          vis[j] = false;
        }
      }
    };
    dfs(0);
    return ans;
  }
};

```

### Python

```python
''' remove an element by its value from a set >>> my_set = {1, 2, 3, 4, 5} >>> my_set.remove(3) >>> print(my_set) {1, 2, 4, 5} ------ cannot remove an element by index from a set in Python3 need to convert the set to a list >>> my_set = {1, 2, 3, 4, 5} >>> my_list = list(my_set) >>> del my_list[2] # remove the element at index 2 >>> my_set = set(my_list) >>> print(my_set) {1, 2, 4, 5} ''' class Solution : # iterative def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: res = [[]] if nums is None or len ( nums ) == 0 : return ans for num in nums : new_res = [] for perm in res : for i in range ( len ( perm ) + 1 ): new_perm = perm [: i ] + [ num ] + perm [ i :] new_res . append ( new_perm ) res = new_res return res ############## class Solution : # iterative, single_perm.insert(index, num) def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: ans = [[]] if nums is None or len ( nums ) == 0 : return ans for num in nums : tmp_list = [] for single_perm in ans : for index in range ( len ( single_perm ) + 1 ): single_perm . insert ( index , num ) tmp_list . append ( single_perm . copy ()) single_perm . pop ( index ) ans = tmp_list return ans ############## ''' In Python 3, both the discard() and remove() methods of a set object are used to remove an element from the set, but there is one key difference: * discard() removes the specified element from the set if it is present, but does nothing if the element is not present. * remove() removes the specified element from the set if it is present, but raises a KeyError exception if the element is not present. >>> a {33, 66, 11, 44, 22, 55} >>> a.discard(22) >>> a {33, 66, 11, 44, 55} >>> a.discard(200) >>> >>> a.remove(200) Traceback (most recent call last): File "<stdin>", line 1, in <module> KeyError: 200 ''' ''' >>> v1 = set([]) >>> v2 = set() >>> >>> v1 set() >>> v2 set() ''' class Solution : def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: res = [] visited = set ([]) def dfs ( nums , path , res , visited ): if len ( path ) == len ( nums ): res . append ( path + []) return for i in range ( 0 , len ( nums )): if i not in visited : visited . add ( i ) path . append ( nums [ i ]) dfs ( nums , path , res , visited ) path . pop () visited . discard ( i ) # remove(i) will throw exception if i not existing dfs ( nums , [], res , visited ) return res ############ class Solution : def permute ( self , nums : List [ int ]) -> List [ List [ int ]]: def dfs ( i ): if i == n : ans . append ( t [:]) return for j in range ( n ): if not vis [ j ]: vis [ j ] = True t [ i ] = nums [ j ] dfs ( i + 1 ) vis [ j ] = False n = len ( nums ) vis = [ False ] * n t = [ 0 ] * n ans = [] dfs ( 0 ) return ans
```