# 2ms Java recursion without backtracking

• 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 {
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);
}
}
}
``````

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