0526. Beautiful Arrangement

# 526. Beautiful Arrangement#

## 题目 #

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:

1. The number at the i position is divisible by i.th
2. i is divisible by the number at the i position.th

Now given N, how many beautiful arrangements can you construct?

Example 1:

``````Input: 2
Output: 2
Explanation:

The first beautiful arrangement is [1, 2]:

Number at the 1st position (i=1) is 1, and 1 is divisible by i (i=1).

Number at the 2nd position (i=2) is 2, and 2 is divisible by i (i=2).

The second beautiful arrangement is [2, 1]:

Number at the 1st position (i=1) is 2, and 2 is divisible by i (i=1).

Number at the 2nd position (i=2) is 1, and i (i=2) is divisible by 1.
``````

Note:

1. N is a positive integer and will not exceed 15.

## 题目大意 #

• 第 i 位的数字能被 i 整除
• i 能被第 i 位上的数字整除

## 解题思路 #

• 这一题是第 46 题的加强版。由于这一题给出的数组里面的数字都是不重复的，所以可以当做第 46 题来做。
• 这题比第 46 题多的一个条件是，要求数字可以被它对应的下标 + 1 整除，或者下标 + 1 可以整除下标对应的这个数字。在 DFS 回溯过程中加入这个剪枝条件就可以了。
• 当前做法时间复杂度不是最优的，大概只有 33.3%

## 代码 #

``````
package leetcode

// 解法一 暴力打表法
func countArrangement1(N int) int {
res := []int{0, 1, 2, 3, 8, 10, 36, 41, 132, 250, 700, 750, 4010, 4237, 10680, 24679, 87328, 90478, 435812}
return res[N]
}

// 解法二 DFS 回溯
func countArrangement(N int) int {
if N == 0 {
return 0
}
nums, used, p, res := make([]int, N), make([]bool, N), []int{}, [][]int{}
for i := range nums {
nums[i] = i + 1
}
generatePermutation526(nums, 0, p, &res, &used)
return len(res)
}

func generatePermutation526(nums []int, index int, p []int, res *[][]int, used *[]bool) {
if index == len(nums) {
temp := make([]int, len(p))
copy(temp, p)
*res = append(*res, temp)
return
}
for i := 0; i < len(nums); i++ {
if !(*used)[i] {
if !(checkDivisible(nums[i], len(p)+1) || checkDivisible(len(p)+1, nums[i])) { // 关键的剪枝条件
continue
}
(*used)[i] = true
p = append(p, nums[i])
generatePermutation526(nums, index+1, p, res, used)
p = p[:len(p)-1]
(*used)[i] = false
}
}
return
}

func checkDivisible(num, d int) bool {
tmp := num / d
if int(tmp)*int(d) == num {
return true
}
return false
}

``````

Apr 8, 2023