Backtracking + Bit Manipulate Java Solution

• ``````public class Solution {
private void rec(int ret, List<Integer> ans, int cnt, int limit, int start) {
int hh = (ret & 15);
int mm = (ret >> 4);
if(hh >= 12 || mm >= 60) {
return;
}
if(cnt == 0) {
//System.out.println(ret);
return;
}

for(int i = start; i < limit; i ++) {
if((ret & (1 << i)) == 0) {
rec(ret | (1 << i), ans, cnt-1, limit, i + 1);
}
}
}

private String convert(int input) {
String h = String.valueOf(input & 15);
String m = String.valueOf(input >> 4);
return h + ":" + (m.length() == 1 ? ("0" + m) : m);
}

private List<String> convert(List<Integer> input) {
List<String> ret = new ArrayList<>();
for(int n : input) {
}
return ret;
}

List<Integer> ans = new ArrayList<>();
rec(0, ans, num, 10, 0);
//System.out.println(ans);
return convert(ans);
}
}
``````

Use the first 10 bit of an integer to represent the watch.
The first 4 bits are the hour
The second 6 bits are minutes

Then feed the number to a very standard backtracking recursion.

Several things to notice:

1. You have to make sure the generated number is a valid time in watch 16:61 is not acceptable.
2. Make sure the backtracking will not generate duplicated number. I use a start var to de-dup.

Problem Solved.

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