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:

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

Back Tracking Solution:

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):

Image for post
Image for post
(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:

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

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

Image for post
Image for 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:

Image for post
Image for post

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.

Image for post
Image for post

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:

Image for post
Image for post

and the result:

Image for post
Image for post

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:

Image for post
Image for post

as we can see the change in the process:

Image for post
Image for post

and the result:

Image for post
Image for post

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:

Image for post
Image for post

Essentially, it means brute force:

Image for post
Image for post

and their relation is like this:

Image for post
Image for post

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!

Written by

Life is beautiful!

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store