本文目录 ⌄
回溯类思路
- ①画出递归树，找到状态变量(回溯函数的参数)，这一步非常重要※
- ②根据题意，确立结束条件
- ③找准选择列表(与函数参数相关),与第一步紧密关联※
- ④判断是否需要剪枝
- ⑤作出选择，递归调用，进入下一层
- ⑥撤销选择
①画出递归树，找到状态变量
灯的数目是越来越少的，参数这里可以使用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;
}
}
};