Leetcode 526: Beautiful Arrangement

https://leetcode.com/problems/beautiful-arrangement/description/

Notes:

This question needs backtracking. But one improvement can be added by memorization.

Let us see the code without memorization first:

class Solution {
public:
    int countArrangement(int N) {
        int res = 0, indx = 0;
        vector<int> visit(N, 0);
        dfs(indx, N, visit, res);
        return res;
    }

private:
    void dfs(int indx, int N, vector<int> &visit, int &res) {
        if(indx == N) {
            ++res;
            return;
        }
        for(int i=1; i<=N; ++i) {
            if(visit[i-1]) continue;
            if(!(i%(indx+1)) || !((indx+1)%i)) {
                visit[i-1] = 1;
                dfs(indx+1, N, visit, res);
                visit[i-1] = 0;
            }
        }
    }
};

Memorization can be applied to this question: let us think about two cases. One is that we put 1 at position 1, and 2 at position 2, and the rest are placed at positions from 3 to n. The other is that we put 2 at position 1, and 1 at position 2, and the res are placed at positions from 3 to n. So in this two cases, the state for the rest elements except 1 and 2 are the same. One of the fundamental is: for the same state, we just need to calculate once.

In this situation, we can use bit-mapping to represent the states.

See the code below:

class Solution {
public:
    int countArrangement(int N) {
        int id = 0, visit = 0;
        vector<int> memo(1<<N, -1);//for each bit, 0 means not selected, 1 selected;
        return dfs(id, N, visit, memo);
    }

private:
    int dfs(int id, int &N, int visit, vector<int> &memo) {
        if(id == N) return 1;
        if(memo[visit] != -1) return memo[visit];
        int t = 0;
        for(int i=1; i<=N; ++i) {
            if((visit>>(i-1)) & 1) continue;
            if(!(i%(id+1)) || !((id+1)%i)) {
                t += dfs(id+1, N, visit | (1<<(i-1)), memo);
            }
        }
        return memo[visit] = t;
    }
};