LeetCode 526. Beautiful Arrangement

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/02/28/LeetCode-526-Beautiful-Arrangement/

访问原文「LeetCode 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 ith position is divisible by i.
2. i is divisible by the number at the ith position.
   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从1开始。给定一个数字N，计算有多少个这样的排布。

解法分析

这道题的主要解法就是回溯，回溯的核心是使用一个数组（假设叫used），这个数组表示这个排布中的某一个数字（用数组下标表示）是否被使用，因为从1开始，所以数组的长度为N+1。

先从第1个位置找合适的数字，如果数字合适然后这个数字没有被使用则将used数组对应下标设为已使用，以此类推。回溯的时候只需要将前面使用的标记为未使用就可以了。

解题代码

	public int countArrangement(int N) {
	if (N == 0) {
		return 0;
	}
	int[] used = new int[N + 1];

	return findRight(N, 1, used);
}

private int findRight(int maxNumber, int position, int[] used) {
	if (position > maxNumber) {
		return 1;
	}

	int rightNumber = 0;
	for (int i = 1; i <= maxNumber; i++) {
		if (used[i] == 0 && (position % i == 0 || i % position == 0)) {
			used[i] = 1;
			rightNumber += findRight(maxNumber, position + 1, used);
			used[i] = 0;
		}
	}
	return rightNumber;
}