Problem description:

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]
Note:
The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

Solution:

We can use backtracking to solve this problem.

  1. Think hours and minutes as a combined array.
  2. Like a combination problem. If we want to pick n elements from hours and minutes, we will pick n-i elements from minutes while we pick i elements from hours.
  • example: if n= 2:
    1
    2
    3
    4
    ["3:00","5:00","9:00","1:01","1:02", ...]`
     1+2:00 ,1+4:00,1+8:00, 1:01
                            i=4(equal to hour.size())
                            generate minute then call helper again
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<int> hour = {1, 2, 4, 8}, minute = {1, 2, 4, 8, 16, 32};
public:
    vector<string> readBinaryWatch(int num) {
        vector<string> res;
        helper(res, make_pair(0, 0), num, 0);
        return res;
    }
    
    void helper(vector<string>& res, pair<int, int> time, int num, int start_point) {
        if (num == 0) {
            res.push_back(to_string(time.first) +  (time.second < 10 ?  ":0" : ":") + to_string(time.second));
            return;
        }
        for (int i = start_point; i < hour.size() + minute.size(); i++)
            if (i < hour.size()) {    
                time.first += hour[i];
                if (time.first < 12)     helper(res, time, num - 1, i + 1);     // "hour" should be less than 12.
                time.first -= hour[i];
            } else {     
                time.second += minute[i - hour.size()];
                if (time.second < 60)    helper(res, time, num - 1, i + 1);     // "minute" should be less than 60.
                time.second -= minute[i - hour.size()];
            }
    }
};

reference: