JAVA code: 76ms. Base on backtracking, and 2D boolean array


  • 0
    C
    public int countArrangement(int N) {
            boolean[][] b = new boolean[N + 1][N + 1];
            for (int i = 1; i <= N; i++) {
                for (int j = i; j <= N; j += i) {
                    b[i][j] = true;
                    b[j][i] = true;
                }
            }
            return backtrack(new boolean[N + 1], 1, b);
        }
    
        public int backtrack(boolean[] used, int curIndex, boolean[][] b) {
            if (curIndex == used.length) return 1;
            int sum = 0;
            for (int i = 1; i < used.length; i++) {
                if (!used[i] && (b[i][curIndex] || b[curIndex][i])) {
                    used[i] = true;
                    sum += backtrack(used, curIndex + 1, b);
                    used[i] = false;
                }
            }
            return sum;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.