526.md

526. Beautiful Arrangement

Solution 1 (time O(n!), space O(n^2))

# DFS
class Solution(object):
    def countArrangement(self, n):
        """
        :type n: int
        :rtype: int
        """
        self.ans = 0
        nums = list(range(1, n + 1))
        self._permute(nums, 1)
        return self.ans

    def _permute(self, nums, ind):
        if len(nums) == 0:
            self.ans += 1
            return
        for i, num in enumerate(nums):
            if num % ind == 0 or ind % num == 0:
                self._permute(nums[:i] + nums[i + 1:], ind + 1)