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:

1
2
3
4
5
6
7
8
9
10
11
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.

思路

在这一题中，我们利用回溯算法来解决问题。

回溯算法和穷举的方法有点类似，利用递归的方式，指定限制条件从而可以在问题集当中递归地访问，从而得出问题的可行解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution(object):
    def countArrangement(self, N):
        """
        :type N: int
        :rtype: int
        """
        search = []
        visited = []
        for i in range(1,N+1):
            tmp1 = []
            tmp2 = []
            a = i
            b = N
            while(b):
                if (b % a == 0):
                    tmp1.append(b)
                    tmp2.append(False)
                b -= 1
            b = N
            while(b):
                if (a % b == 0):
                    if (a != b):
                        tmp1.append(b)
                        tmp2.append(False)
                b -= 1
            search.append(tmp1)
            visited.append(tmp2)
           
        x = y = 0
        ans = 0
        res = 0 
        for y, enum in enumerate(search[0]):
            ans = 0
            result = []
            res += self.backtracking(result, search, x, y, ans)
            
        return res
        
    def backtracking(self, result, search, x, y, ans):
        for i in result:
            if (search[x][y] == i):
                return ans
                
        result.append(search[x][y])
        
        if (x  < len(search) - 1):
            for i, enum in enumerate(search[x+1]):
                ans = self.backtracking(result, search, x+1, i, ans)
            result.pop()
            
            return ans
        else:
            result.pop()
            ans += 1
            return ans

参考资料：http://www.cnblogs.com/wuyuegb2312/p/3273337.html