simple recursive java solution with O(N!) time complexity


  • 0
    G

    No special thing, just count every possible permutation. Welcome smarter solution!!!

    public class Solution {
        int count = 0;
        public int countArrangement(int N) {
            boolean[] visited = new boolean[N + 1];
            helper(N, visited, 1);
            return count;
        }
        public void helper(int N, boolean[] visited, int len) {
            if (len == N + 1) {
                count++;
                return;
            }
            for (int i = 1; i <= N; i++) {
                if (!visited[i] && (i % len == 0 || len % i == 0)) {
                    visited[i] = true;
                    helper(N, visited, len + 1);
                    visited[i] = false;
                }
            }
        }
    }
    

Log in to reply
 

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