Easy Backtracking Solution with Comments


  • 4
    S
    public class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res=new ArrayList();
        if(num>8){  //impossible if num>8 because the max time is 11:59
            return res;
        }
        if(num==0){
            String ans="0:00";    //return the basic situation of num=0
            res.add(ans);
            return res;
        }
        int temp[]={8,4,2,1,32,16,8,4,2,1};//hours and minutes in an array!
        boolean index[]=new boolean[10];//boolean array to check if used!
        helper(res,temp,index,num,0);
        return res;
    }
    void helper(List<String> res,int[] temp,boolean[] index,int num,int start){
        if(num==0){//num=0,it is time to return answers!
            int hour=0;
           int minute=0;
            for(int k=0;k<10;k++){
                if(index[k]==true&&k<=3){
                    hour+=temp[k];
                }
                if(index[k]==true&&k>3){
                    minute+=temp[k];
                }
            }
            if(hour>=12||minute>=60){//impossible cases!
                return;
            }
            else{//Two situations of minutes to add to the string!!
                if(minute<10){
                    String answer=""+hour+":"+"0"+minute;
                    res.add(answer);
                    return;
                }
                else{
                    String answer=""+hour+":"+minute;
                    res.add(answer);
                    return;
                }
                    
                }
            }
        for(int i=start;i<temp.length;i++){//Backtracking Loop from here!
            index[i]=true;
            helper(res,temp,index,num-1,i+1);
            index[i]=false;
        }
    }
    

    }


  • 0
    T

    I think it is recrusive dfs, not loop backtracking


  • 0
    C

    share the similar idea with you


Log in to reply
 

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