# Permutations

## Problem

Given an array `nums` of distinct integers, return *all the possible permutations*. You can return the answer in **any order**.

{% hint style="info" %}
For example:

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

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

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

{% endhint %}

### Thought Process

* We are essentially picking and placing the number in a seperate list and recursing on the new list without that number present

## Solution

```
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        soln = []
        self.helper(nums, [], soln)
        return soln
    
    def helper(self, nums, permList, soln):
        
        if len(nums) == 0:
            soln.append(list(permList))
            return
        for i in range(len(nums)):
            permList.append(nums[i])
            remaining = nums[:i] + nums[i+1:]
            self.helper(remaining,permList,soln)
            permList.pop()
```

## Key Points

* In our for-loop, we separate the specific number from the rest of the numbers, append the seperated number to our new list, and recurse on the new seperated list

## Time Complexity

* **Time:** $$O(n\*n!)$$ 
* **Space:** $$O(n \* n!)$$