C++_Backtracking_Accepted


  • 0
     class Solution {
     public:
        vector<int> hours = {1,2,4,8};
        vector<int> minutes = {1,2,4,8,16,32};
        
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        if(num >= 9 || num < 0) return res;
        find(num, res, hours, minutes, 0, 0, 0);
        return res;
    }
    
    void find(int num, vector<string>& res, vector<int> hours, vector<int> minutes, int hour, int minute, int begin){
        if(num == 0){
            string path = to_string(hour) + ':' + (minute >= 10 ? to_string(minute) : '0' + to_string(minute));
            res.push_back(path);return;
        }
        
        for(int i = begin; i < hours.size() + minutes.size(); i++){
            if(i < hours.size()){
                 hour += hours[i];
                 if(hour < 12){
                      find(num - 1, res, hours, minutes, hour, minute, i+1);
                  }
                  hour -= hours[i];
            }
            else{
                minute += minutes[i - hours.size()];
                if(minute < 60){
                    find(num - 1, res, hours, minutes, hour, minute, i+1);
                }
                minute -= minutes[i - hours.size()];
            }
        }
    }  };
    

    /*

    Thanks for Mad_air (https://discuss.leetcode.com/topic/59373/0ms-c-back-tracking-solution-easy-to-understand) solution.

    At first I thought I should divide num into two numbers, num1 + num2 = num, and then use the two different numbers as the chosen numbers from hours and minutes. But this method is too complex.

    The backtracking method just first check all possible solutions for hours, and then check the possible results for minutes.

    It's a good practice for backtracking method.

    */


Log in to reply
 

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