Simple Java backtracking solution


  • 0
    L

    It's highly structured and almost all backtracking methods follow similar patterns.

        List<String> rlt = new ArrayList();
        public List<String> readBinaryWatch(int num) {
        	dfs(0, 0, 0, num, 0, new boolean[10]);
            return rlt;
        }
    
       public void dfs(int hh, int mm, int level, int max_level, int index, boolean[] used){
        	if(level == max_level){
        	    if(hh <= 11 && mm <= 59){
        	        if(mm<=9) rlt.add(hh +":0" + mm);
        	        else rlt.add(hh + ":" + mm);
                }
                return;
            }
            for(int i=index; i<10; i++){
            	if(!used[i]){
            	    used[i] = true;
            	    if(i<=3) dfs(hh + (int)Math.pow(2,i), mm, level+1, max_level, i+1, used);
            	    else dfs(hh, mm + (int)Math.pow(2,i-4), level+1, max_level, i+1, used);
            	    used[i] = false;
                    }
            }
        }
    

Log in to reply
 

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