Problem description:

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

Example 1:

1
2
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:

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

Example 3:

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

Constraints:

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

Solution:

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrack(nums, res, path):
            if not nums:
                res.append(path)
                return
            for i in range(len(nums)):
                backtrack(nums[:i]+ nums[i+1:], res, path+[nums[i]])
        res = []
        backtrack(nums, res, [])
        return res

Time complexity explain

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/d782127d-4909-4418-9f52-198608b60c0a/Untitled.png

https://leetcode.com/problems/permutations/discuss/993970/Python-4-Approaches-%3A-Visuals-%2B-Time-Complexity-Analysis

  1. In order to reaverse the tree, will visit each node once, we know very well that would cost us O(N) in a binary tree and O(E+V) in an N-ary tree where V = vertices and E = edges (or number of children). Now for the [1,2,3] example shown in the sketch, we can see there is a total of 16 nodes/verticies and that |E| varies from level to level with an upper limit of N and a lower limit of 1.
    • So, we can say roughly O(E+V) = a little more than 16
    • O(N!) on the other hand = 6
    • whereas, $O(NN!)! = 36 = 18
  2. Another way of looking at is we know from set theory that there are N! permutations of a list of size N. We also know that the permutations are going to be the leaves of the tree, which means we will have N! leaves. In order to get to each one of those leaves, we had to go through N calls. That’s O(N*N!). Again a little more than the total number of nodes because some nodes are shared among more than one path.

time complexity: $O(N*N!)$
space complexity: $O()$
reference: