My solution with Backtracking


  • 0
    L

    But I don't know how to make the check generic and simple ...

    public int numberOfPatterns(int m, int n) {
    	int result = 0;
    	for (int i = m; i <= n; i++) {
    		result += count(i);
    	}
    
    	return result;
    }
    
    private int count(int i) {
    	boolean[] candidates = new boolean[9];
    
    	return impl(candidates, i, -1);
    }
    
    private int impl(boolean[] candidates, int i, int last) {
    	if (i == 0) {
    		return 1;
    	}
    
    	int result = 0;
    	for (int j = 0; j < 9; j++) {
    		if (!candidates[j]) {
    			if (last == -1 || check(candidates, last, j)) {
    				candidates[j] = true;
    				result += impl(candidates, i - 1, j);
    				candidates[j] = false;
    			}
    		}
    	}
    
    	return result;
    }
    
    private boolean check(boolean[] candidates, int i, int j) {
    	if (i > j) {
    		return check(candidates, j, i);
    	}
    
    	if (i / 3 == j / 3) {
    		for (int k = i + 1; k < j; k++) {
    			if (!candidates[k]) {
    				return false;
    			}
    		}
    	}
    
    	if (i % 3 == j % 3) {
    		for (int k = i + 3; k < j; k += 3) {
    			if (!candidates[k]) {
    				return false;
    			}
    		}
    	}
    
    	if (!candidates[4] && (i == 0 && j == 8 || i == 2 && j == 6)) {
    		return false;
    	}
    
    	return true;
    }

Log in to reply
 

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