LeetCode 526 Beautiful Arrangement

LeetCode

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] = 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

题目大意：

求数组中所有排列中下标（从1开始）和数值能整除（下标整除数值或反之）的个数

解题思路：

一开始考虑用DP，因为求个数且类似于L368 Largest Divisible Subset，但问题与子问题的具体排位有关，所以DP不可行。考虑用Stack，但数组顺序可变。
只能用暴力法，也就是DFS中排列求解

解题步骤：

N/A

注意事项：

1. 用排列模板，但此题不涉及具体数组。用set来记录访问过的数值而不是下标，start来记录模拟结果path中的位置

Python代码：

def countArrangement(self, n: int) -> int:
	return self.permute(n, 1, set())

def permute(self, n, start, visited): # 2, 1, [F,F,F]
	if start == n + 1: # remember n + 1
		#print(path)
		return 1
	res = 0 # 1
	for i in range(1, n + 1): # [1,3)
		if i in visited:
			continue
		if i % start == 0 or start % i == 0:
			visited.add(i)
			#path.append(i)
			res += self.permute(n, start + 1, visited) # 2, 2, [FFT]
			#path.pop()
			visited.remove(i)
	return res

算法分析：

时间复杂度为O(解大小)，空间复杂度O(n)