Beautiful Arrangement Back Tracking Not So Fast Java Solution


  • 1
    W

    The basic idea is to try every possible combination and check how many of them are valid. My idea is to use backtracking, which might exceed time limit, but note that, in the question, it says N is no larger than 15. So, give it a try.

    int totalCount = 0;
    public int countArrangement(int N) {
    	int[] array = new int[N];
    	for (int i = 1; i <= N; i++) {
    		array[i - 1] = i;
    	}
    	int pos = 1;
    	for (int i = 1; i <= N; i++) {
    		if (i % pos == 0 || pos % i == 0) {
    			array[i - 1] = -1;
    			loopThrough(array, pos + 1, N);
    			array[i - 1] = i;
    		}
    	}
    	return totalCount;
    }
    
    private void loopThrough(int[] array, int pos, final int N) {
    	if (pos > N) {
    		totalCount++;
    	}
            for (int i = 1; i <= N; i++) {
    		if (array[i - 1] != -1 && (array[i - 1] % pos == 0 || pos % array[i - 1] == 0)) {
    			array[i - 1] = -1;
    			loopThrough(array, pos + 1, N);
    			array[i - 1] = i;
    		}
    	}
    }
    

Log in to reply
 

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