Missing undo step on backtrack
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.
Build confidence with an intuition-first walkthrough focused on backtracking fundamentals.
A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.
"4:51".Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.
The hour must not contain a leading zero.
"01:00" is not valid. It should be "1:00".The minute must consist of two digits and may contain a leading zero.
"10:2" is not valid. It should be "10:02".Example 1:
Input: turnedOn = 1 Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]
Example 2:
Input: turnedOn = 9 Output: []
Constraints:
0 <= turnedOn <= 10Problem summary: A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right. For example, the below binary watch reads "4:51". Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order. The hour must not contain a leading zero. For example, "01:00" is not valid. It should be "1:00". The minute must consist of two digits and may contain a leading zero. For example, "10:2" is not valid. It should be "10:02".
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Backtracking · Bit Manipulation
1
9
letter-combinations-of-a-phone-number)number-of-1-bits)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #401: Binary Watch
class Solution {
public List<String> readBinaryWatch(int turnedOn) {
List<String> ans = new ArrayList<>();
for (int i = 0; i < 12; ++i) {
for (int j = 0; j < 60; ++j) {
if (Integer.bitCount(i) + Integer.bitCount(j) == turnedOn) {
ans.add(String.format("%d:%02d", i, j));
}
}
}
return ans;
}
}
// Accepted solution for LeetCode #401: Binary Watch
func readBinaryWatch(turnedOn int) []string {
var ans []string
for i := 0; i < 12; i++ {
for j := 0; j < 60; j++ {
if bits.OnesCount(uint(i))+bits.OnesCount(uint(j)) == turnedOn {
ans = append(ans, fmt.Sprintf("%d:%02d", i, j))
}
}
}
return ans
}
# Accepted solution for LeetCode #401: Binary Watch
class Solution:
def readBinaryWatch(self, turnedOn: int) -> List[str]:
return [
'{:d}:{:02d}'.format(i, j)
for i in range(12)
for j in range(60)
if (bin(i) + bin(j)).count('1') == turnedOn
]
// Accepted solution for LeetCode #401: Binary Watch
impl Solution {
pub fn read_binary_watch(turned_on: i32) -> Vec<String> {
let mut ans: Vec<String> = Vec::new();
for i in 0u32..12 {
for j in 0u32..60 {
if (i.count_ones() + j.count_ones()) as i32 == turned_on {
ans.push(format!("{}:{:02}", i, j));
}
}
}
ans
}
}
// Accepted solution for LeetCode #401: Binary Watch
function readBinaryWatch(turnedOn: number): string[] {
const ans: string[] = [];
for (let i = 0; i < 12; ++i) {
for (let j = 0; j < 60; ++j) {
if (bitCount(i) + bitCount(j) === turnedOn) {
ans.push(`${i}:${j.toString().padStart(2, '0')}`);
}
}
}
return ans;
}
function bitCount(i: number): number {
i = i - ((i >>> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
i = (i + (i >>> 4)) & 0x0f0f0f0f;
i = i + (i >>> 8);
i = i + (i >>> 16);
return i & 0x3f;
}
Use this to step through a reusable interview workflow for this problem.
Generate every possible combination without any filtering. At each of n positions we choose from up to n options, giving nⁿ total candidates. Each candidate takes O(n) to validate. No pruning means we waste time on clearly invalid partial solutions.
Backtracking explores a decision tree, but prunes branches that violate constraints early. Worst case is still factorial or exponential, but pruning dramatically reduces the constant factor in practice. Space is the recursion depth (usually O(n) for n-level decisions).
Review these before coding to avoid predictable interview regressions.
Wrong move: Mutable state leaks between branches.
Usually fails on: Later branches inherit selections from earlier branches.
Fix: Always revert state changes immediately after recursive call.