Suppose you have
n integers labeled
n. A permutation of those
perm (1-indexed) is considered a beautiful arrangement if for every
1 <= i <= n), either of the following is true:
perm[i]is divisible by
iis divisible by
Given an integer
n, return the number of the beautiful arrangements that you can construct.
Input: n = 2 Output: 2 Explanation: The first beautiful arrangement is [1,2]: - perm = 1 is divisible by i = 1 - perm = 2 is divisible by i = 2 The second beautiful arrangement is [2,1]: - perm = 2 is divisible by i = 1 - i = 2 is divisible by perm = 1
Input: n = 1 Output: 1
1 <= n <= 15
Use the backtracking approach to find all the combinations where each position meets nums[i] is divisible by i or i is divisible by nums[i] condition.
class Solution: def countArrangement(self, n: int) -> int: numbers = [i for i in range(1, n + 1)] results =  visited = set() self.helper(results, numbers, , visited) return len(results) def helper(self, results, numbers, combination, visited): if len(combination) == len(numbers): results.append(list(combination)) return for num in numbers: if num in visited: continue if num % (len(combination) + 1) != 0 and (len(combination) + 1) % num != 0: continue combination.append(num) visited.add(num) self.helper(results, numbers, combination, visited) combination.pop() visited.remove(num)
- Time Complexity: O(N).
- Space Complexity: O(N).