本文共 2560 字，大约阅读时间需要 8 分钟。

题目：

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:

　The number at the ith position is divisible by i.

　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:

N is a positive integer and will not exceed 15.

解释：

1.arr[i]能够被i整除，i = 1, 2, …, N2.i能够被arr[i]整除，i = 1, 2, …, N 2.pos%i==0 or i%pos==0 ,pos表示当前的位置，i表示当前可用的数字 简单分析该题可以发现，将N个数字放置在N个位置上，这样的问题是较为典型的回溯问题：假设前i个数字已经放置好（满足条件1或条件2），则对于第i+1个位置，如果能从还未被放置的数字集合unused（或visited）中找到一个满足条件的数字k，则将其放在第i+1个位置，同时将k从unused中去掉（或者将visited[k - 1]标记为true），继续对第i+2执行相同的操作（通过递归调用）；如果找不到满足条件的数字，则回溯到上一层，修改第i个位置的数字，再尝试第i+1个位置···依此类推。 递归的base case应当是递归树的高度达到了N，如果当前层次为第N层，则表示从0到N-1层得到的这条路径是一个Beautiful Arrangement，count++。 python代码：

class Solution(object):    def countArrangement(self, N):        """        :type N: int        :rtype: int        """        self.visited=[False]*N        self.count=0        self.N=N        def dfs(pos):            if pos==0:                self.count+=1                return            for i in xrange(1,self.N+1):                #如果当前数字已经被使用或者两个条件都不满足                if(self.visited[i-1] or (pos%i!=0 and i%pos!=0)):                    continue                #当前数字可以使用                #深入                self.visited[i-1]=True                dfs(pos-1)                #回溯                self.visited[i-1]=False        dfs(N)        return self.count

c++代码：

class Solution {
   public:    int count=0;    int global_N;    vector
   
     visited;    int countArrangement(int N) {
           global_N=N;        visited=vector
    
     (N,false);        dfs(N);        return count;    }    void dfs(int pos)    {
           if (pos==0)            count++;        for(int i=1;i<=global_N;i++)        {
               if(visited[i-1] ||(i%pos!=0 && pos%i!=0) )                continue;            else             {
                   visited[i-1]=true;                dfs(pos-1);                visited[i-1]=false;            }        }    }};
    
   

总结：

转载地址：http://jwmcn.baihongyu.com/