Java Backtracking Solution


  • 0
    D
    public class Solution {
        private int[] hour = new int[] {1,2,4,8};
        private int[] min = new int[] {1,2,4,8,16,32};
    
        public List<String> readBinaryWatch(int num) {
            List<String> res = new ArrayList<>();
            
            for(int i = 0; i <= num; i++) {
                if (i <= 4 && num - i <= 6) {
                    List<String> hours = new ArrayList<>();
                    List<String> mins = new ArrayList<>();
                    backTrackHours (i, 0, 0, hours, 0);
                    backTrackMins (num - i, 0, 0, mins, 0);
                    for (String h : hours) {
                        for (String m : mins) {
                            if (!res.contains(h + ":" + m)) {
                                res.add(h + ":" + m);
                            }
                        }
                    }
                }
            }
            return res;
        }
        
        private void backTrackHours (int totayNum, int start, int alreadyUsed, List<String> hours, int sum) {
            if (totayNum == 0) {
                hours.add("0");
                return;
            }
            if (alreadyUsed == totayNum && sum < 12) {
                hours.add(Integer.toString(sum));
                return;
            }
            for (int i = start; i < hour.length; i++) {
                sum += hour[i];
                backTrackHours(totayNum, i + 1, alreadyUsed + 1, hours, sum);
                sum -= hour[i];
            }
        }
        
        private void backTrackMins (int totayNum, int start, int alreadyUsed, List<String> mins, int sum) {
            if (totayNum == 0) {
                mins.add("00");
                return;
            }
            if (alreadyUsed == totayNum && sum < 60) {
                if (sum < 10) {
                    mins.add("0" + Integer.toString(sum));
                } else {
                    mins.add(Integer.toString(sum));
                }
                return;
            }
            for (int i = start; i < min.length; i++) {
                sum += min[i];
                backTrackMins (totayNum, i + 1, alreadyUsed + 1, mins, sum);
                sum -= min[i];
            }
        }
    }
    

Log in to reply
 

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