Crack Leetcode 401: Binary Watch

There is a way to make it easy.

Sometimes they make it look hard, while in fact, there’s always a way you can easily understand. Today, we’ll crack leetcode 401 — Binary Watch — together. After this article, you’ll have a better understanding of Back Tracking. Without further ado, let’s get started.

Problem Description:

(photo taken from Leetcode: https://leetcode.com/problems/binary-watch/)

Back Tracking Solution:

Ideation:

There are 4 LEDs in hour, and 6 LEDs in minute. In total there needs to be this many (N) LEDs on. So we just find all the combinations for N LEDs, and give out the reading time in required format.

The question is how to find all the combinations. Here we used Back Tracking to find all possible hours(or minutes):

(inspired by this post: https://leetcode.com/problems/binary-watch/discuss/88456/3ms-Java-Solution-Using-Backtracking-and-Idea-of-%22Permutation-and-Combination%22)

This code means if say: getAllPossibleSum([32,16,8,4,2,1], 3), then it will find all possible combinations of three digits, and store the sum into a list, then return that list.

So if we integrate this code into our solution, it would be like this:

Python Code:

(inspired by this post: https://leetcode.com/problems/binary-watch/discuss/88456/3ms-Java-Solution-Using-Backtracking-and-Idea-of-%22Permutation-and-Combination%22)

Complexity Analysis:

Since for this problem, the input num can’t be +oo. There are only limited possibilities, as shown in this post:

(photo taken from https://leetcode.com/problems/binary-watch/discuss/88475/sorry-I-cheat..)

I don’t see it be of any meaning to analyze time and space complexity.

Understand Back Tracking:

Here I’ll use “generating nCr” as an example:

BT(or noBT ) holds the newly found possible combination in string format. For example, in 5C3, a possible value for BT(or noBT) is “012”.

The only difference between BT and noBT lies in the moment when going to the next recursion.

For BT, the input changed to BT+str(i), but BT itself doesn’t change. Whereas for noBT, the input changed to same value by changing the value of noBT.

This difference is key. Because now BT can go back to previous state, but noBT can’t go to the correct previous state, as we can see from the process:

and the result:

Therefore, if we want to backtrack, we can’t modify the parameter value before next recursion, UNLESS we change it back right after this recursion:

as we can see the change in the process:

and the result:

Back Tracking Logic:

I’ll still use “generating nCr” as an example. Let’s say generate 5C3. If we use back tracking, it looks like this:

Essentially, it means brute force:

and their relation is like this:

With Back Tracking, we now only need one for loop, instead of many in the brute force.

The End:

Thanks for reading! Please check our articles more often, if you’d like to support our work — and we’ll see you in the next one!