leetcode 526优美的数列

题目

leetcode 526优美的数列c++

假设有从 1 到 N 的 N 个整数，若是从这 N 个数字中成功构造出一个数组，使得数组的第 i 位 (1 <= i <= N) 知足以下两个条件中的一个，咱们就称这个数组为一个优美的排列。条件：web

第 i 位的数字能被 i 整除
i 能被第 i 位上的数字整除
如今给定一个整数 N，请问能够构造多少个优美的排列？数组

示例1:svg

输入: 2
输出: 2
解释:code

第 1 个优美的排列是 [1, 2]:
第 1 个位置（i=1）上的数字是1，1能被 i（i=1）整除
第 2 个位置（i=2）上的数字是2，2能被 i（i=2）整除xml

第 2 个优美的排列是 [2, 1]:
第 1 个位置（i=1）上的数字是2，2能被 i（i=1）整除
第 2 个位置（i=2）上的数字是1，i（i=2）能被 1 整除leetcode

说明:
N 是一个正整数，而且不会超过15。get

回溯分析

• 穷举每一个位置符合规则的数字
• 节点的解空间：[1~N]
• 终止条件： 路径的长度 大于 N
• 解的判断条件：每一个节点选择的数字都符合规则，则当终止时，该路径就是一个优美数列
• 减枝： 已经使用过的数字或者 不符合2条规则的，掠过
• 回溯的状态：每一个数字都只能在用一次，用used数组记录数字的使用状况

code

class Solution {
    int counter = 0;
    void backtrace(char used[],int N,int level){
        if(level > N){
            counter++;
            return;
        }
        for(int i = 1; i <= N;++i){
        	//已经使用过
            if(used[i] > 0 || (i % level != 0 && level % i != 0))continue;
            used[i] = 1;
            backtrace(used,N,level + 1);
            used[i] = 0;
        }
    }
public:
    int countArrangement(int N) {
        char* used = new char[N+1];
        memset(used,N+1,0);
        backtrace(used,N,1);
        delete [] used;
        return counter;
    }
};