text: """
  526
  beautiful arrangement
  medium
  
  backtracking
  
  20210607
  
  Suppose you have n integers labeled 1 through n. A permutation of those n integers
  perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n),
  either of the following is true:
  
  perm[i] is divisible by i.
  i is divisible by perm[i].
  Given an integer n, return the number of the beautiful arrangements that you can construct.
  """
  
  
  class Solution:
      def countArrangement(self, n: int) -> int:
  
          S = {i: None for i in range(1, n+1)}
          count = 0
  
          def backtracking(S):
  
              nonlocal count
  
              if len(S) == 0:
                  count += 1
  
              i = n - len(S) + 1
              for num in S.copy():
                  if num % i == 0 or i % num == 0:
                      del S[num]
                      backtracking(S)
                      S[num] = None
  
          backtracking(S)
          return count
  
  
  sol = Solution()
  print(sol.countArrangement(4))