Java Backtracking


  • 1

    We incrementally fill out each index array position [1..N], trying out each possible number. We however do not try a number in a position if it is violates the given constraints.

        public int countArrangement(int N) {
        	return backtrack(new boolean[N], 0);
        }
        
        public int backtrack(boolean[] used, int curIndex) {
            if (curIndex == used.length) return 1;
            int sum = 0;
            for (int i=0;i<used.length;i++) {
                if (!used[i] && ((i+1) % (curIndex+1) == 0 || (curIndex + 1) % (i+1) == 0)) {
                    used[i] = true;
                    sum += backtrack(used, curIndex + 1);
                    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.