## 526. 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 by `i`.
• `i` is divisible by `perm[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 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
```

Example 2:

```Input: n = 1
Output: 1
```

Constraints:

• `1 <= n <= 15`

## Rust Solution

``````struct Solution;

impl Solution {
fn count_arrangement(n: i32) -> i32 {
let mut res = 0;
let mut nums = (1..=n).collect();
let n = n as usize;
Self::dfs(0, &mut nums, &mut res, n);
res
}

fn dfs(start: usize, nums: &mut Vec<i32>, all: &mut i32, n: usize) {
if start == n {
*all += 1;
} else {
for i in start..n {
if nums[i] % (start as i32 + 1) == 0 || (start as i32 + 1) % nums[i] == 0 {
nums.swap(start, i);
Self::dfs(start + 1, nums, all, n);
nums.swap(start, i);
}
}
}
}
}

#[test]
fn test() {
let n = 2;
let res = 2;
assert_eq!(Solution::count_arrangement(n), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.