401.二进制手表

题目

回溯类思路

• ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
• ②根据题意，确立结束条件
• ③找准选择列表(与函数参数相关),与第一步紧密关联※
• ④判断是否需要剪枝
• ⑤作出选择，递归调用，进入下一层
• ⑥撤销选择

①画出递归树，找到状态变量

灯的数目是越来越少的，参数这里可以使用num计数，当num减少到0时输出结果。index指示当前选择的节点。使用pair存储小时和分钟。

void backtrace(int num,int index,pair<int,int> &time){}

②根据题意，确立结束条件

 if(num==0){   
          if(time.first>11||time.second>59)
            return;
            string temp_hour=to_string(time.first);
            string temp_minute=to_string(time.second);
            if(temp_minute.size()==1){
               temp_minute.insert(0,"0");
            }
            ans.push_back(temp_hour+":"+temp_minute);
            return;
      }

③找准选择列表(与函数参数相关)

vector<int> watch={1,2,4,8,1,2,4,8,16,32};//前四号是小时，后面是分钟的二进制值

for(int i=index;i<10;i++){
     //一共十个待选项
}

④判断是否需要剪枝

 for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
       
 }

⑤作出选择，递归调用，进入下一层

 for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
         if(i<4){
             time.first+=watch[i];
         }else{
             time.second+=watch[i];
         }
         backtrace(num-1,i+1,time); //这里是i+1，之前的已经选过了
}

⑥撤销选择

 for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
         pair<int,int> temp=time;
         if(i<4){
             time.first+=watch[i];
         }else{
             time.second+=watch[i];
         }
         backtrace(num-1,i+1,time);
         time=temp;
 }

全部代码

class Solution {
 public:
  vector<string> ans;
  vector<int> watch={1,2,4,8,1,2,4,8,16,32};
  vector<string> readBinaryWatch(int num) {
      pair<int,int>time(0,0);
      backtrace(num,0,time);
      return ans;
  }
  void backtrace(int num,int index,pair<int,int> &time){
      if(num==0){   
          if(time.first>11||time.second>59)
            return;
            string temp_hour=to_string(time.first);
            string temp_minute=to_string(time.second);
            if(temp_minute.size()==1){
               temp_minute.insert(0,"0");
            }
            ans.push_back(temp_hour+":"+temp_minute);
            return;
      }
      for(int i=index;i<10;i++){
       if(time.first>11||time.second>59)
            break;
         pair<int,int> temp=time;
         if(i<4){
             time.first+=watch[i];
         }else{
             time.second+=watch[i];
         }
         backtrace(num-1,i+1,time);
         time=temp;
      }
  }
};

执行结果