Java Backtracking solution


  • 0
    Z
    public class Solution {
        public int countArrangement(int N) {
    		boolean[] avail = new boolean[N+1];
    		for(int i=0; i<N+1; i++) avail[i] = true;
    		return count(N, avail);
        }
    	
    	public int count(int N, boolean[] avail){
    		if(N<=0) return 0;
    		if(N==1) return 1;
    		int res = 0;
    		int M = avail.length;
    		boolean clear = false;
    		while(M-->1){
    			if(avail[M]&&(N%M == 0 || M%N == 0)){
    				avail[M] = false;
    				clear = true;
    				res+=count(N-1,avail);
    			}
    			if(clear){
    			    avail[M] = true;
    			    clear = false;
    			}
    			
    		}
    		return res;
    	}
    }
    

Log in to reply
 

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