LeetCode/特别的排列

给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0

1. 记忆化搜索 + 状态压缩

class Solution {
public:
    int specialPerm(vector<int>& nums) {
        int mod = 1e9+7;
        int m = nums.size();
        int memo[m][m<<14];
        memset(memo, -1, sizeof(memo));
        function<int(int, int,int)> f = [&](int pre, int mask,int depth) -> int {
            if (depth==m) //边界条件一
                return 1;
            if (pre!=-1&&memo[pre][mask] != -1) //已经存储过，直接剪枝返回
                return memo[pre][mask];
            int res = 0; //计算无重复数字
            
            //做选择
            for (int j = 0; j < nums.size(); j++) //遍历数做选择
                if ((mask & 1<<j) == 0){ // j 不在 mask 中
                        if(pre==-1||nums[pre]%nums[j]==0||nums[j]%nums[pre]==0)
                            res = (res + f(j, mask | (1 << j),depth+1)%mod)%mod;
                }
            if(pre!=-1)
                memo[pre][mask] = res%mod;
            return res;
        };
        
        return f(-1, 0,0);   //从下标-1开始，初始状态为空，
    }
};