leetcode 526. Beautiful Arrangement 递归实现全排列 + 经典深度优先遍历DFS做法

﹏ヽ暗。殇╰゛Y 2022-06-03 03:21 188阅读 0赞

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.

本题题意很简单，直接深度优先遍历DFS即可

建议和[leetcode 667. Beautiful Arrangement II 双指针遍历][leetcode 667. Beautiful Arrangement II]

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    
    using namespace std;
    
    class Solution 
    {
    public:
        int count = 0;
        int countArrangement(int n)
        {
            vector<bool> visit(n + 1, false);
            dfs(visit, 1, n);
            return count;
        }
    
        void dfs(vector<bool>& visit, int index, int size)
        {
            if (index >= size+1)
            {
                count++;
                return;
            }
            else
            {
                for (int i = 1; i <= size; i++)
                {
                    if (visit[i] == false && (index % i == 0 || i % index == 0))
                    {
                        visit[i] = true;
                        dfs(visit, index + 1, size);
                        visit[i] = false;
                    }
                }
            }
        }
    };

[leetcode 667. Beautiful Arrangement II]: http://blog.csdn.net/jackzhang_123/article/details/78871040