## 题目描述

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".

## 解法一

### 思路

``````result = []
for ones_hour in range(0, num + 1):
ones_minute = num - ones_hour
hours = get_combination(4, ones_hour)
minutes = get_combination(6, ones_minute)
for hour in hours:
result.append('%d:%02d' % (hour, minute))``````

``````           ↓      ↓      ↓      ↓
0000 -> 0000 -> 0000 -> 0000 -> 0000 (NO)
1000 (NO)
0100 -> 0100 (NO)
1100 (YES)
0010 -> 0010 -> 0010 (NO)
-> 1010 (YES)
0110 (YES)
0001 -> 0001 -> 0001 -> 0001 (NO)
1001 (YES)
0101 (YES)
0011 (YES)

output: [1100, 1010, 0110, 1001, 0101, 0011]``````

### Python

``````class Solution(object):
"""
:type num: int
:rtype: List[str]
"""
def get_combination(length, num_ones, base, pool):
if num_ones == 0:
pool.append(base)
return
if length == 0 or length < num_ones:
return
get_combination(length - 1, num_ones - 1, base + (1 << (length - 1)), pool)
get_combination(length - 1, num_ones, base, pool)

result = []
for ones_hour in range(0, num + 1):
ones_minute = num - ones_hour
hours = []
minutes = []
get_combination(4, ones_hour, 0, hours)
get_combination(6, ones_minute, 0, minutes)
for hour in hours:
if hour > 11:
continue
for minute in minutes:
if minute > 59:
continue
result.append('%d:%02d' % (hour, minute))
return result``````

### Java

``````public class Solution {
class Utils {
void getCombination(int length, int numOnes, int base, List<Integer> pool) {
if (numOnes == 0) {
return;
}
if (length == 0 || length < numOnes) {
return;
}
getCombination(length - 1, numOnes - 1, base + (1 << (length - 1)), pool);
getCombination(length - 1, numOnes, base, pool);
}
}
Utils utils = new Utils();
List<String> result = new ArrayList<>();
for (int onesHour = 0; onesHour <= num; onesHour++) {
int onesMinute = num - onesHour;
List<Integer> hours = new ArrayList<>();
List<Integer> minutes = new ArrayList<>();
utils.getCombination(4, onesHour, 0, hours);
utils.getCombination(6, onesMinute, 0, minutes);
for (int hour : hours) {
if (hour > 11) {
continue;
}
for (int minute : minutes) {
if (minute > 59) {
continue;
}
}
}
}
return result;
}
}``````

### C++

``````class Solution {
public:
class Utils {
public:
void getCombination(int length, int numOnes, int base, vector<int> &pool) {
if (numOnes == 0) {
pool.push_back(base);
return;
}
if (length == 0 || length < numOnes) {
return;
}
getCombination(length - 1, numOnes - 1, base + (1 << (length - 1)), pool);
getCombination(length - 1, numOnes, base, pool);
}
};
Utils utils;
vector<string> result;
for (int onesHour = 0; onesHour <= num; onesHour++) {
int onesMinute = num - onesHour;
vector<int> hours;
vector<int> minutes;
utils.getCombination(4, onesHour, 0, hours);
utils.getCombination(6, onesMinute, 0, minutes);
for (int hour : hours) {
if (hour > 11) {
continue;
}
for (int minute : minutes) {
if (minute > 59) {
continue;
}
if (minute > 9) {
result.push_back(to_string(hour) + ":" + to_string(minute));
} else {
result.push_back(to_string(hour) + ":0" + to_string(minute));
}
}
}
}
return result;
}
};``````