concise and straight forward backtracking code in Java


  • 0
    S
    public class Solution {
        public List<String> readBinaryWatch(int num) {
            //number of bits in hours [max(0, num - 6), min(num, 4)]
            
            List<String> res = new ArrayList<>();
            int[] hours = {1, 2, 4, 8};
            int[] minutes = {1, 2, 4, 8, 16, 32};
            
            for (int hourBitNum = Math.max(0, num - 6);  hourBitNum <= Math.min(num, 4); hourBitNum++) {
                List<Integer> minutesString = new ArrayList<>();
                List<Integer> hoursString = new ArrayList<>();
                
                helper(hours, hourBitNum, 0, 0, hoursString, 1);
                helper(minutes, num - hourBitNum, 0, 0, minutesString, 0);
                
                for (int i = 0; i < hoursString.size(); i++) {
                    int hour = hoursString.get(i);
                    for (int j = 0; j < minutesString.size(); j++) {
                        int minute = minutesString.get(j);
                        res.add("" + hour + ":" + (minute < 10 ? "0" + minute : minute));
                    }
                }
            }
            
            return res;
        }
        
        //all possible sum of 'bitNum' bit in the 'array' starting from pos;
        public void helper(int[] array, int bitNum, int pos, int sum, List<Integer> res, int type) {
            if (bitNum == 0) {
                res.add(sum);
                return;
            }
            
            //index upper bound is (size - bitNum)
            for (int i = pos; i <= array.length - bitNum; i++) {
                //hours can not be more than 12
                if (type == 1 && sum + array[i] > 11) break;
                //minutes can not be more than 59;
                if (type == 0 && sum + array[i] > 59) break;
                
                helper(array, bitNum - 1, i + 1, sum + array[i], res, type);
            }
        }
    }
    

Log in to reply
 

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