Description
https://leetcode.com/problems/beautiful-arrangement/
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 byi.iis divisible byperm[i].
Given an integer n, return the number of the beautiful arrangements that you can construct.
Example 1:
Input: n = 2
Output: 2
Explanation:
The first beautiful arrangement is [1,2]:
- perm[1] = 1 is divisible by i = 1
- perm[2] = 2 is divisible by i = 2
The second beautiful arrangement is [2,1]:
- perm[1] = 2 is divisible by i = 1
- i = 2 is divisible by perm[2] = 1
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 15
Explanation
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.
Python Solution
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).