Backtracking in java (more complicated than needed)


  • 0
    A

    Explanations in the code comments:

    public class Solution {
        public List<String> readBinaryWatch(int num) {
            // algorithm: simply brutal force all possibilities
            //  first we can only light at most 8 LEDs
            //  (if 9, then either hour is 15=2**4-1, or minute is 63=2**6-1)
            // for hours:
            // 0: 0
            // 1: 1, 2, 4, 8
            // 2: 3, 5, 9, 6, 10, 12
            // 3: 11
            // for minutes
            // 0: 0
            // 1: 1, 2, 4, 8, 16, 32
    
            List<String> result = new ArrayList<>();
    
            if (8 < num) {
                return result;
            }
    
            HashMap<Integer, List<Integer>> possibleHours = possibleSums(new int[]{1,2,4,8}, 12);
            HashMap<Integer, List<Integer>> possibleMinutes = possibleSums(new int[]{1,2,4,8,16,32}, 60);
    
            for (int index = 0; index <= num; index++) {
                int numHours = index;
                int numMinutes = num - index;
    
                List<Integer> hours = possibleHours.get(numHours);
                List<Integer> minutes = possibleMinutes.get(numMinutes);
                if (null == hours || null == minutes) {
                    continue;
                }
                for (int hour : hours) {
                    String strHour = hour + "";
                    for (int minute : minutes) {
                        String strMinute = String.format("%02d", minute);
                        result.add(strHour + ":" + strMinute);
                    }
                }
            }
    
            return result;
        }
    
        // return a hashmap of possible of possible sums given input 1,2,4,8,16,32,
        //  but the sum must be less than the max
        private HashMap<Integer, List<Integer>> possibleSums(int[] elements, int max) {
            HashMap<Integer, List<Integer>> map = new HashMap<>();
            int startIndex = 0;
            List<Integer> numbersTracked = new ArrayList<>();
            int currentSum = 0;
            backtracking(elements, max, map, 0, numbersTracked, currentSum);
            return map;
        }
    
        private void backtracking(int[] elements, int max, HashMap<Integer, List<Integer>> map, int startIndex, List<Integer> numbersTracked, int currentSum) {
            if (numbersTracked.size() <= elements.length) {
                // all elements are added?
                if (currentSum <= max) {
                    List<Integer> listSums = map.get(numbersTracked.size());
                    if (null == listSums) {
                        listSums = new ArrayList<>();
                        map.put(numbersTracked.size(), listSums);
                    }
                    assert null != listSums;
                    listSums.add(currentSum);
                }
            }
    
            for (int index = startIndex; index < elements.length; index++) {
                // make a move
                numbersTracked.add(elements[index]);
                // recursion into next number
                backtracking(elements, max, map, index+1, numbersTracked, currentSum+elements[index]);
                // backtrack to move to next candidate
                numbersTracked.remove(numbersTracked.size()-1);
            }
        }
    }

Log in to reply
 

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