Java Intuitive and Verbose Combination Backtracking


  • 0
    D

    Uses backtracking to generate all T/F combinations of a boolean array of size 10. Once there's no more lights to assign, it calls a function to build the time and add it to the list. It ignore's combinations that contain times that are out of range.

    public class Solution {
        
        private boolean[] state;
        private List<String> times;
        private StringBuilder time;
        
        public Solution() {
            this.state = new boolean[10];
            this.times = new ArrayList<String>();
            this.time = new StringBuilder();
        }
        
        public void addBinaryTimes(int n, int pos) {
            if (n == 0) {
                addTime();
                return;
            }
            
            for (int i = pos; i < 10; i++) {
                if (!state[i]) {
                    state[i] = true;
                    addBinaryTimes(n - 1, i + 1);
                    state[i] = false;
                }
            }
        }
        
        public List<String> readBinaryWatch(int num) {
            this.addBinaryTimes(num, 0);
            return this.times;
        }
        
        private void addTime() {
    		int hour = 0;
            int minute = 0;
            
            for (int i = 0; i < 6; i++) {
                if (this.state[i]) {
                    // Optimization to quickly calculate powers of 2
                    minute += 1 << i;
                }
            }
            
            if (minute >= 60) {
                return;    
            }
            
            for (int i = 0; i < 4; i++) {
                if (this.state[i + 6]) {
                    hour += 1 << i;
                }
            }
            
            if (hour >= 12) {
                return;
            }
            
            this.time.append(hour);
            this.time.append(':');
            if (minute / 10 == 0) {
                this.time.append('0');
            }
            this.time.append(minute);
            
            this.times.add(this.time.toString());
            this.time.setLength(0); // clear SB
        }
    }
    

Log in to reply
 

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