187. Binary Watch

Easy · Backtracking

A binary watch has 10 LEDs: 4 for hours (representing 1, 2, 4, 8) and 6 for minutes (representing 1, 2, 4, 8, 16, 32). Given the number of LEDs that are turned on, find all possible times the watch could display. Hours range from 0–11 and minutes from 0–59. Return all valid times as strings in "h:mm" format, sorted in ascending order. For example, if 1 LED is on, it could represent 0:01 (the 1-minute LED), 0:02 (the 2-minute LED), or 1:00 (the 1-hour LED), among others.

Examples

Example 1
Input: 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
Explanation: Every single-LED state
Example 2
Input: 0
Output: ["0:00"]
Explanation: No LEDs on → midnight

Constraints