---
tags: data_structure_python
---

# Permutations <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a collection of distinct integers, return all possible permutations.

**Example:**

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

## Solution

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def __permute(nums, n, chosen, perms,res):
            if len(perms) == n:
                res.append(perms[:])
            else:
                for i in range(n):
                    if chosen[i]:
                        continue
                    else:
                        chosen[i] = True
                        perms.append(nums[i])
                        __permute(nums, n, chosen, perms, res)
                        perms.pop()
                        chosen[i] = False
            
        n = len(nums)
        res = []
        __permute(nums, n, [False]*n, [], res)
        return res