Java backtrack solution


  • 0
    S
        int result = 0;
        
        public int countArrangement(int N) {
            boolean[][] okay = new boolean[N+1][N+1];
            boolean[] taken = new boolean[N+1];
            int i, j;
            
            for (i=1;i<=N;i++) {
                for (j=1;j<=N;j++) {
                    if (i % j == 0 || j % i == 0) {
                        okay[i][j] = true;
                    }
                }
            }
            
            backtrack(okay, taken, 1, N);
            return result;
        }
        
        public void backtrack(boolean[][] okay, boolean[] taken, int index, int N) {
            if (index > N) {
                result++;
                return;
            }
            int i;
            for (i=1;i<=N;i++) {
                if (!taken[i] && okay[index][i]) {
                    taken[i] = true;
                    backtrack(okay, taken, index + 1, N);
                    taken[i] = false;
                }
            }
        }
    }

Log in to reply
 

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