2ms Java recursion without backtracking


  • 1
    S

    A digit can be 0 only if the number of remaining 1's doesn't exceed the number of remaining digits, so the first recursive call could be avoided sometimes, making it mostly tail recursive without backtracking.

    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> list = new ArrayList<String>();
            foo(10, num, 1, 0, list);
            return list;
        }
        
        // i: number of remaining digits, n: number of remaining 1's
        // x: the actual binary number being built, base = 2^(10-i) passed around just for easier computing
        private void foo(int i, int n, int base, int x, List<String> list) {
            if (i == 0) {
                list.add(x/64+ (x%64>9 ? ":" : ":0") +x%64);
                return;
            }
            if (i > n) foo(i-1, n, base*2, x, list);
            if (n > 0) {
                // hours < 12, so 1st & 2nd digits can't be all 1
                if (i == 1 && (x&(base/2)) != 0) return;
                // minutes < 60, so 5, 6, 7, 8-th digits can't be all 1
                if (i == 5 && ((x&(base/2))*(x&(base/4))*(x&(base/8))) != 0) return;
                foo(i-1, n-1, base*2, x+base, list);
            }
        }
    }
    

Log in to reply
 

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