[打卡]8.16_526.优美的排列

相关题解:优美的排列

image-20210816014748728

AC代码:

class Solution {
private:
    int res = 0;
    bool st[16];//最大是1~15整数,标记数组
    void dfs(int start, int n) {
        if (start > n) {//如果步数大于n,则找到一个满足条件的序列
            res++;
            return;
        }
        for (int i = 1; i <= n; i++) {//从1~n个整数中找寻满足条件的i
            if (!st[i] && (i % start == 0 || start % i == 0)) {//若该数字之前未被使用且满足条件
                st[i] = true;//则将它标记
                dfs(start + 1, n);//进行下一步
                st[i] = false;//回溯
            }
        }
    }
public:
    int countArrangement(int n) {
        memset(st, false, sizeof st);
        dfs(1, n);
        return res;
    }
};

认真读题,简单递归回溯

本文链接:

https://nullcode.fun/171.html
1 + 6 =
快来做第一个评论的人吧~