在上一篇题解中，我总结了回溯算法的三种类型，以及什么时候用回溯算法，怎么写回溯算法，如果没看过的，强烈建议先看：C++ 总结了回溯问题类型 带你搞懂回溯算法(大量例题)

这一节，我们就来解析“搜索”类型的回溯问题。

为什么要单独分出一种“搜索”类型？

其实，“搜索”类型的题解中都能看到“子集”、“排列”类型题目的影子，只要你搞懂前面两种类型问题的本质，就很容易联想到了。“搜索”类型的问题最难的就是把问题抽象化！！大多数比赛或者面试题中不会直接出现“子集、排列、组合”等字眼，更不会直接让去求，而是通过某些包装，借助某个情景，让你一下子摸不着头脑，看不出应该使用哪种解法，本题就是最好的说明

解题步骤：
1.读懂题意，把题目尽可能抽象成“子集、排列、组合”类型问题
本题的题目总结而言就是：有十盏灯，我分别给他编号0-9，号码0-3代表小时，号码4-9代表分钟，然后每盏灯又代表着不同数字，如下图

(灯泡中的红色数字,其实就是二进制转换，题目中的图也有标)
然后从10盏灯中挑选n盏打开，问你有多少种组合，返回这些组合代表的时间。这样一翻译，是不是有点“组合”类型问题的味道了？说白了就是：从n个数里面挑选k个，返回组合。如果你能形成这种抽象思想，那么你就成功一大半了。

2.回溯六步走

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

3.开始解题
①递归树，这里用动画演示。假设n=2，即选两盏灯亮
<,,,,,,,,,,,,>

我们接下来思考，回溯函数需要什么哪些参数，来表示当前状态。首先灯是越来越少的，所以需要一个参数num,表示剩余可亮的灯数，直到num等于0就应该结束；然后还需要参数start，来指示当前可选择的灯的开始位置，比如n=2我选了7号灯,然后剩下的一盏灯，只能选8号或9号，你不可能回去选0-6号，因为会导致重复，这个问题在“子集、组合”类型问题中说过，详细请看顶部的文章；最后还需要一个time参数，来表示当前状态的时间。算法签名如下

###cpp

unordered_map<int,int> hash={{0,1},{1,2},{2,4},{3,8},{4,1},{5,2},{6,4},{7,8},{8,16},{9,32}};//用一个hash表映射，灯对应的数字
void backtrack(int num,int start,pair<int,int>& time)//我用stl中的pair结构来统一管理小时和分钟，代码比较简洁，你也可以把他们拆成两个参数，hour和minute

②根据题意，确立结束条件
这个上面提到过了，当num=0就是没有灯可以点亮了，就应该return，加入结果集

###cpp

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)//如果minute只有一位要补0，注意题目要求
                temp_minute.insert(0,"0");
            res.push_back(temp_hour+":"+temp_minute);//构造格式
            return;
        }

③找准选择列表
从参数start标识的位置开始，到最后一盏灯，都是可选的

###cpp

for(int i=start;i<10;i++)
{


}

④判断是否需要剪枝
当hour>11或minute>59的时候，无论还有没有灯可以点亮，都不用再继续递归下去，因为后面只会越增越多，应该剪枝

###cpp

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

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

###cpp

 for(int i=start;i<10;i++)
    {
        if(time.first>11||time.second>59)
            continue;
        pair<int,int>store=time;//保存状态,用于回溯时，恢复当前状态
        if(i<4)//对小时数进行操作
            time.first+=hash[i];
        else//对分钟数进行操作
            time.second+=hash[i];
        backtrack(num-1,i+1,time);//进入下一层，注意下一层的start是i+1，即从当前灯的下一盏开始

⑥撤销选择
整体代码如下

###cpp

vector<string>res;
    unordered_map<int,int> hash={{0,1},{1,2},{2,4},{3,8},{4,1},{5,2},{6,4},{7,8},{8,16},{9,32}};
    void backtrack(int num,int start,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)//如果minute只有一位要补0
                temp_minute.insert(0,"0");
            res.push_back(temp_hour+":"+temp_minute);//构造格式
            return;
        }
    
        for(int i=start;i<10;i++)
        {
            if(time.first>11||time.second>59)
                continue;
            pair<int,int>store=time;//保存状态
            if(i<4)
                time.first+=hash[i];
            else
                time.second+=hash[i];
            backtrack(num-1,i+1,time);//进入下一层，注意下一层的start是i+1，即从当前灯的下一盏开始
            time=store;//恢复状态
        }
    }
    vector<string> readBinaryWatch(int num) {
        pair<int,int>time(0,0);//初始化时间为0:00
        backtrack(num,0,time);
        return res;
    }