C++ Recursive Backtracking Solution, 0ms


  • 0
    F
    vector<string> readBinaryWatch(int num) {
          vector<string> result;
          vector<int> candidates(10,0);
          BinaryWatch_helper(candidates,0,result,num,0);            
          return result;
        }    
        void BinaryWatch_helper(vector<int>& candidates,int start,vector<string>& result, int num, int count)
        {		
            if(count==num){
    			int hour_count=0;
    			for (int i = 0; i <= 3; i++) {
    				if (candidates[i] == 1) {
    					hour_count += pow(2, i);
    				}
    			}			
    			int minute_count=0;
    			for (int i = 4; i <= 9; i++) {
    				if (candidates[i] == 1) {
    					minute_count += pow(2, i-4);
    				}
    			}			
                if(hour_count<12 && minute_count<60){
    			    string str="";
    			    if(minute_count>=10)
    				    str+=to_string(hour_count)+":"+to_string(minute_count);
    			    else
    				    str+=to_string(hour_count)+":0"+to_string(minute_count);
                    result.push_back(str);
                    return;
                }  
            }
            for(int i=start;i<candidates.size();i++){        
                candidates[i]=1;
                BinaryWatch_helper(candidates,i+1,result,num, count+1);
                candidates[i]=0;      
            }
        }
    

Log in to reply
 

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