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
Related Topics:
Backtracking, Depth-first Search
Similar Questions:
The brute force way is to generate all the permutations and check each permutation's validity. This will take O(N!) time and get TLE.
We can improve it by backtracking once we see invalid prefix.
// OJ: https://leetcode.com/problems/beautiful-arrangement/
// Author: github.com/lzl124631x
// Time: O(K) where K is the number of valid permuataions
// Space: O(N)
class Solution {
int dfs(vector<int> &v, int start) {
if (start == v.size()) return 1;
int ans = 0;
for (int i = start; i < v.size(); ++i) {
if (v[i] % (start + 1) && (start + 1) % v[i]) continue;
swap(v[i], v[start]);
ans += dfs(v, start + 1);
swap(v[i], v[start]);
}
return ans;
}
public:
int countArrangement(int n) {
vector<int> v(n);
iota(begin(v), end(v), 1);
return dfs(v, 0);
}
};