C++ Backtracking Solution using Bit Manipulation


  • 0
    E
    class Solution {
    public:
        vector<string> readBinaryWatch(int num) 
        {
            vector<string> result;
            do_read(num, 0, 0, result);
            return result;
        }
        
        void do_read(int num, int begin, int time, vector<string> &result)
        {
            int minute = time & 0x3f, hour = (time & ~0x3f) >> 6;//time : 4bits    hour : 6bits  0x3f == 00111111b
            if (minute > 59 || hour > 11)  return;
            if (num == 0)
            {
                result.push_back(to_string(hour) + (minute < 10 ? ":0" : ":") + to_string(minute));
                return;
            }
            
            for (int i = begin; i < 10; i++)
            {
                int mask = 1 << i;
                time |= mask;
                do_read(num - 1, i + 1, time, result);
                time &= ~mask;
            }
        }
    };
    

Log in to reply
 

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