Simple Java solution


  • 0
    L

    With an example of [1,2,3], you will realize that it tries all combinations. A new combination is tried with the constraint and backtracked to find another suitable combination. Here is the java code:

        private int count;
        public int countArrangement(int N) {
            arrangement(1, N, new HashSet < Integer > ());
            return count;
        }
    
    
    
        private boolean arrangement(int pos, int n, Set < Integer > set) {
            if (set.size() == n) {
                count++;
                return true;
            }
            for (int i = 1; i <= n; i++) {
                if (set.contains(i)) {
                    continue;
                }
                if (i % pos == 0 || pos % i == 0) {
                    set.add(i);
                    arrangement(pos + 1, n, set);
                    set.remove(i);
                }
            }
            return false;
        }
    

Log in to reply
 

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