Clean & Simple Java Backtracking Solution


  • 0
    H
    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> times = new ArrayList<>();
            if(num > 8) return times;
    
            // We want the hours to use from 0-3 LEDs
            // We also want the minutes to use from 0-5 LEDs
            //
            // Therefore, the hours should start with Math.max(0, (num-5)) and only go up to 3
            // We can't have less than 0 LEDs
            // And since we are increasing the hour's LEDs, the minutes need to start with as many as possible, which is 5
            for(int i = Math.max(0, (num - 5)); i < 4; i++) {
                List<String> hours = new ArrayList<>();
                backtrack(hours, 0, 1, 8, 11, i, false);
                
                List<String> minutes = new ArrayList<>();
                backtrack(minutes, 0, 1, 32, 59, num - i, true);
                
                for(String s : hours) {
                    for(String m : minutes) {
                        times.add(s + ":" + m);
                    }
                }
            }
            return times;
        }
        
        public void backtrack(List<String> units, int currUnit, int nextUnit, int endUnit, int maxUnit, int bitsLeft, boolean isMinutes) {
            if(bitsLeft == 0) {
                if(isMinutes && currUnit < 10) {
                    units.add(String.valueOf("0" + currUnit));
                } else {
                    units.add(String.valueOf(currUnit));
                }
                return;
            }
            for(int i = nextUnit; i <= endUnit && (currUnit + i) <= maxUnit; i *= 2) {
                backtrack(units, currUnit + i, i*2, endUnit, maxUnit, bitsLeft-1, isMinutes);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.