[Java] Back Tracking / T : O(N^N), S : O(N)


  • 0
    J
    public class Solution {
        public int countArrangement(int N) {
            boolean[] used = new boolean[N];
            return backTrackArrangement(N, 1, used);
        }
        
        public int backTrackArrangement(int N, int cur, boolean[] used){
            if(cur > N)
                return 1;
            
            int sum = 0;
            for(int i = 0; i < N; i++){
                if(used[i] == false && (cur % (i+1) == 0 || (i+1) % cur == 0)){
                    used[i] = true;
                    sum += backTrackArrangement(N, cur+1, used);
                    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.