Java N! solution using backtracking, any better time complexity?


  • 0
    J
        int count;
        public int countArrangement(int N) {
            if(N <= 2) {
                return N;
            }
            count = 0;
            backtrack(N, 1, new boolean[N]);
            return count;
        }
        
        private void backtrack(int N, int level, boolean[] used) {
            if(level > N) {
                count++;
                return;
            }
            for(int i = 1; i <= N; i++) {
                if(used[i - 1]) {
                    continue;
                }
                if(i % level == 0 || level % i == 0) {
                    used[i - 1] = true;
                    backtrack(N, level + 1, used);
                    used[i - 1] = false;
                }
            }
        }
    } ```

Log in to reply
 

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