LeetCode #526: Beautiful Arrange

Problem

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.

题意

输入整数N，表示有N个数需要放置在N个位置上（数字和位置的下标都是从1到N），如果能够找出一个序列中任意一个数都满足以下两个条件中的一个，则将这个序列称为一个Beautiful Arrangement：

1. arr[i]能够被i整除，i = 1, 2, ..., N
2. i能够被arr[i]整除，i = 1, 2, ..., N

对于给出的N，要求计算出共有多少种Beautiful Arrangement.

分析

简单分析该题可以发现，将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++。

Code

对于回溯同样也有不同的实现，下面贴出两段代码，都用到了回溯的思想，但在具体的实现上有所不同。

使用visited

//主要的思想是从后向前开始递归，即递归树的根节点是最后一个元素
//使用visited数组标识数字i是否已经被使用过

//Runtime: 19ms
class Solution {
private:
    vector<bool> visited;
    int count;
    void _dfs(int N, int nextPos){
        if (nextPos == 0){
            count++;
            return;
        }
        for (int i = 1; i <= N; i++){
            //该数字已经被使用 || 两个条件都不满足
            if (visited[i - 1] || nextPos % i != 0 && i % nextPos != 0)
                continue;
            visited[i - 1] = true;
            //深入
            _dfs(N, nextPos - 1);
            //回溯
            visited[i - 1] = false;
        }
    }
public:
    int countArrangement(int N){
        count = 0;
        visited.resize(N);
        for (int i = 0; i < N; i++) visited[i] = false;
        _dfs(N, N);
        return count;
    }
};

使用swap

//这是Solution中效率很高的一份代码，贴在这里以供学习
//同样是从后向前，这个解法的作者使用swap函数代替了visited数组，主要思路如下：
//1. 初始化一个数组容器v，存放的元素为[1...N]（不包括0）
//1. 假设后面的下标从p+1到N-1的位置都已经放置好，考虑下标为p的位置
//2. for(int i = 0; i < p; i++) 遍历从v[0]到v[p-1]的数，如果v[i]满足条件，则将v[i]与v[p-1]交换
//3. 再次递归时，需要考虑的就只是下标从0到p-1的位置该如何放置了
//4. 返回结果时，再将v[i]与v[p-1]交换回来

//Runtime: 6ms
class Solution {
private:
    int _count(int n, vector<int>& v){
        if (n <= 1)    return 1;
        int result = 0;
        for (int i = 0; i < n; i++){
            if (v[i] % n == 0 || n % v[i] == 0){
                swap(v[i], v[n - 1]);
                result += _count(n - 1, v);
                swap(v[i], v[n - 1]);
            }
        }
        return result;
    }
public:
    int countArrangement(int N) {
        vector<int> v;
        v.resize(N);
        for (int i = 0; i < N; i++)    v[i] = i + 1;
        return _count(N, v);
    }
};