Problem statement

https://leetcode.com/problems/permutations/

Solution

Let us try to built our sequence element by element, inserting new element in different places.

Complexity

Time and space complexity is O(n! * n).

Code

class Solution:
    def permute(self, nums):
        def dfs(ind, built):
            if ind == len(nums):
                ans.append(built)
                return
            
            for i in range(ind+1):
                dfs(ind + 1, built[:i]+[nums[ind]]+built[i:])
                
        ans = []
        dfs(0, [])
        return ans