Simple Java Backtracking!


  • 0
    S
    public class Solution {
        public List<String> readBinaryWatch(int n) {
            int[] time = new int[] {1, 2, 4, 8, 1, 2, 4, 8, 16, 32};
            List<String> res = new ArrayList();
            backtrack(res, time, 0, n, 0, 0, 0);
            return res;
        }
        
        private void backtrack(List<String> res, int[] time, int start, int n, int hour, int min, int count) {
            if (hour > 11 || min > 59) {
                return;
            }
            if (count == n) {
                String mm = min < 10 ? "0" + min : "" + min;
                String hh = "" + hour;
                res.add(new String(hh + ":" + mm));
                return;
            }
            
            for (int i = start; i < time.length; i++) {
                int newHour = i < 4 ? hour + time[i] : hour;
                int newMin = i < 4 ? min : min + time[i];
                backtrack(res, time, i + 1, n, newHour, newMin, count + 1);
            }
        }
    }
    

Log in to reply
 

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