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 integernwhich 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: 类似subset,只向后看
public List<String> readBinaryWatch(int num) {
List<String> ans = new ArrayList<>();
int[] time = {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};
helper(0, 0, 0, time, num, ans);
return ans;
}
private void helper(int index, int hour, int minute, int[] time, int num, List<String> ans) {
if (num == 0) {
if (minute < 10) {
ans.add(hour + ":0" + minute);
} else {
ans.add(hour + ":" + minute);
}
return;
}
for (int i = index; i < 10; i++) {
if (i < 4) {
if (hour + time[i] < 12) {
helper(i + 1, hour + time[i], minute, time, num - 1, ans);
}
} else {
if (minute + time[i] < 60) {
helper(i + 1, hour, minute + time[i], time, num - 1, ans);
}
}
}
}