526 Beautiful Arrangement
Last updated
Was this helpful?
Last updated
Was this helpful?
Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:
The number at the ith position is divisible by i.
i is divisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?
Example 1:
Note:
N is a positive integer and will not exceed 15.
(1) Backtracking
Backtracking: 时间复杂度O(N!), 空间复杂度O(N)