Leetcode # 46. Permutations

2023.08.02
★★ Medium Backtracking LeetCode Memoization Permutation Recursion

https://leetcode.com/problems/permutations

Solution

Time Complexity: O(n * n!)

n := len(nums)
nums 的排列有 n! 種，每一種的長度皆為 n

Space Complexity: O(n)

recursion call stack 的最大 depth 為 n
output 所使用的空間不計入 space complexity

(The input and output generally do not count towards the space complexity.)

class Solution:
  def permute(self, nums: List[int]) -> List[List[int]]:
    permutations = {}
    def _permute(l):
      t_l = tuple(l)
      if t_l not in permutations:  
        if len(l) < 2:
          permutations[t_l] = [l]
        else:
          permutations[t_l] = []
          for i, e in enumerate(l):
            permutations[t_l] += ([[e] + _l for _l in _permute(l[:i] + l[i + 1:])])
      return permutations[t_l]
      
    return _permute(nums)

Leetcode # 46. Permutations

Solution

相關例題