二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。

每个 LED 代表一个 0 或 1，最低位在右侧。

例如，上面的二进制手表读取 “3:25”。

给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。

示例：

输入: n = 1
返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

提示：

• 输出的顺序没有要求。
• 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
• 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
• 超过表示范围（小时 0-11，分钟 0-59）的数据将会被舍弃，也就是说不会出现 “13:00”, “0:61” 等时间。

Solution

参考 @liuyubobobo 、**@ljj666** 、@detachmliu

• 回溯法

// @lc code=start
class Solution {
private:
    vector<string> res;
public:
    vector<string> readBinaryWatch(int num) {
        vector<bool> bits(10, false);
        dfs(bits, 0, num);
        return res;
    }

private:
    void dfs(vector<bool>& bits, int index, int num){
        if(index==10){
            int h = 0;
            for(int i=0; i<4; ++i)
                h = h*2 + bits[i];
            int m = 0;
            for(int i=4; i<10; ++i)
                m = m*2 + bits[i];
            
            if(h<12 && m<60){
                char time[6];
                sprintf(time, "%d:%02d", h, m);
                res.push_back(string{time});
            }
            return;
        }

        if(10-index > num)
            dfs(bits, index+1, num);
        if(num){
            bits[index] = true;
            dfs(bits, index+1, num-1);
            bits[index] = false;
        }
        return;
    }
};
// @lc code=end

• 暴力法

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        //直接遍历  0:00 -> 12:00   每个时间有多少1
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (count1(i) + count1(j) == num) {
                    res.push_back(to_string(i)+":"+
                                  (j < 10 ? "0"+to_string(j) : to_string(j)));
                }
            }
        }
        return res;
    }
    //计算二进制中1的个数
    int count1(int n) {
        int res = 0;
        while (n != 0) {
            n = n & (n - 1);
            res++;
        }
        return res;
    }
};