3ms C++ Solution using the idea of generating PnC with backtracking


  • 1
    L
    class Solution {
    public:
        vector<bool> time; // first four bits for hours..remaining four bits for minutes
        vector<string> ans;
        string t;
        void solve(int num, int start, int index)
        {
            if(num<=0)
            {
                int hour=0,mins=0;
                for(int i=0;i<4;i++) hour+=pow(2,i)*time[i];
                for(int i=4;i<10;i++) mins+=pow(2,i-4)*time[i];
                if(hour>11 || mins>59)  return;
                t=to_string(mins);
                if(mins/10==0) t="0"+t;
                t=to_string(hour)+":"+t;    
                ans.push_back(t);
                return;
            }
            for(int i=start;i<10;i++)
            {
                time[i]=1;
                solve(num-1,i+1,index+1);
                time[i]=0;
            }
        }
        
        vector<string> readBinaryWatch(int num) {
            time.resize(10,0);
            solve(num,0,0);
            return ans;
        }
    };
    

Log in to reply
 

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