# 3ms Java Solution Using Backtracking and Idea of "Permutation and Combination"

• ``````public class Solution {
List<String> res = new ArrayList<>();
int[] nums1 = new int[]{8, 4, 2, 1}, nums2 = new int[]{32, 16, 8, 4, 2, 1};
for(int i = 0; i <= num; i++) {
List<Integer> list1 = generateDigit(nums1, i);
List<Integer> list2 = generateDigit(nums2, num - i);
for(int num1: list1) {
if(num1 >= 12) continue;
for(int num2: list2) {
if(num2 >= 60) continue;
res.add(num1 + ":" + (num2 < 10 ? "0" + num2 : num2));
}
}
}
return res;
}

private List<Integer> generateDigit(int[] nums, int count) {
List<Integer> res = new ArrayList<>();
generateDigitHelper(nums, count, 0, 0, res);
return res;
}

private void generateDigitHelper(int[] nums, int count, int pos, int sum, List<Integer> res) {
if(count == 0) {
return;
}

for(int i = pos; i < nums.length; i++) {
generateDigitHelper(nums, count - 1, i + 1, sum + nums[i], res);
}
}
}
``````

• big god

• This is the best answer.
"Get all combinations from a list, each combination contains 'num' non-duplicate elements" can be used every where.

• I can't agree with you more. How can you think of this? Can you tell me how can improve my backtracking thought

• Brilliant idea!
I also made some improvement here:
change the code below:

``````for(int i = 0; i <= num; i++) {
``````

into

``````for(int i = 0; i <= num && i <= nums1.length; i++) {
``````

• @pford You can also add the following after it:

``````if(num - i > nums2.length) continue;
``````

• Hi, I want to know what's the time complexity of your solution? thank you

• @weihanzh I'm not too sure, maybe O(n * h * m)?
Loop n times then loop for each hour and minute

• Many people got a slow running time like 33ms because they are suing slow io method.(The method "String.format"). After replacing with the statement "num1 + ":" + (num2 < 10 ? "0" + num2 : num2", I also get fast running time: 4ms.

• what is the time complexity?

• This post is deleted!

• Thanks for sharing.

• Similar ideas with you, easy to understand

``````public class Solution {
List<String> result = new ArrayList<>();
if(num == 0){
return result;
}

for(int i = 0; i <= num; i++ ){
List<String> hours = getHours(i);
List<String> minutes = getMinutes(num - i);

for(String hour : hours){
for(String minute : minutes){
String temp = hour + ":" + minute;
}
}
}

return result;
}

int[] hourDict = new int[]{8,4,2,1};
int[] minuteDict = new int[]{32,16,8,4,2,1};

private List<String> getHours(int num){
List<String> list = new ArrayList<>();
hourHelper(hourDict, 0, 0, 0, num, list);
return list;
}

private void hourHelper(int[] array, int curSum, int index, int level, int num, List<String> list){
if(level == num && curSum < 12){
return;
}
for(int i = index; i < array.length; i++){
curSum += array[i];
hourHelper(array, curSum, i+1, level+1, num, list);
curSum -= array[i];
}
}

private List<String> getMinutes(int num){
List<String> list = new ArrayList<>();
minuteHelper(minuteDict, 0, 0, 0, num, list);
return list;
}

private void minuteHelper(int[] array, int curSum, int index, int level, int num, List<String> list){
if(level == num && curSum < 60){
String temp = curSum < 10 ? ("0" + Integer.toString(curSum)) : String.valueOf(curSum);
return;
}
for(int i = index; i < array.length; i++){
curSum += array[i];
minuteHelper(array, curSum, i+1, level+1, num, list);
curSum -= array[i];
}
}
}
``````

• @Hellokitty_2015 Sorry I don't understand the logic, could you or somebody explain me please?

• Thanks for sharing! How about we use only 1 integer to represent the watch?

``````    public List<String> readBinaryWatch(int num) {
List<String> ret = new ArrayList<>();
dfs(ret, 0, num, 0);
return ret;
}

private void dfs(List<String> ret, int path, int num, int k) {
int hr = (path & 0xF), min = (path & 0xFF0) >> 4;
if (hr > 11 || min > 59) return;
if (num == 0) {
ret.add(hr + ":" + (min < 10 ? "0": "") + min);
} else {
for (int i = k; i < 10; i++) {
dfs(ret, (path | (1 << i)), num - 1, i + 1);
}
}
}
``````

• @cdai Thanks for your sharing, my solution below is inspired from you

``````public List<String> readBinaryWatch(int num) {
List<String> result = new ArrayList<>();
for(int i=0;i<=num;i++){
ArrayList<Integer> hour = new ArrayList<>();
ArrayList<Integer> minute = new ArrayList<>();
generateTime(i,0,8, hour);
generateTime(num-i,0,32,minute);
for(int num1: hour) {
if(num1 >= 12) continue;
for(int num2: minute) {
if(num2 >= 60) continue;
result.add(num1 + ":" + (num2 < 10 ? "0" + num2 : num2));
}
}
}
return result;
}

public void generateTime(int count, int sum, int max, ArrayList<Integer> timeList){
if(count == 0){