526. Beautiful Arrangement

Description

image-20210816183414471

Solution

  1. Naively do backtracking

  2. DP + State Compression

    use mask to record first num ‘s integer’s combinations, for example

    0101 means 1 and 3 are in the first 2 slots of the array. 

    1
    dp[mask] = sum of dp[mask^i], which i is suitable for popcount(mask) slot

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int countArrangement(int n) {
        vector<unordered_set<int>> suitable(n+1);
        for(int i = 1; i <= n;i ++){
            for(int j = 1; j <= n; j++){
                if(i % j == 0 || j % i == 0)
                    suitable[i].insert(j);
            }
        }
        unordered_set<int> visited;
        return backtracking(n,1,visited, suitable);
    }

    int backtracking(int n, int curPos, unordered_set<int>& visited, const vector<unordered_set<int>>& suitable){
        if(curPos == n+1)
            return 1;
        int res = 0;
        for(int i = 1; i <= n; i++){
            if(visited.count(i) || suitable[curPos].count(i) == 0)
                continue;
            visited.insert(i);
            res += backtracking(n, curPos+1, visited, suitable);
            visited.erase(i);
        }
        return res;
    }
};

Solution2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int countArrangement(int n) {
        vector<int> dp(1 << n);
        dp[0] = 1;
        for(int mask = 0; mask < (1 <<n); mask++){
            int num = __builtin_popcount(mask);
            for(int i = 0; i < n; i++){
                if((mask & (1<<i)) && (num % (i+1) == 0 || (i+1) % num == 0)){
                    dp[mask] += dp[mask^(1<<i)];
                }
            }
        }
        return dp[(1<<n) - 1];
    }
};