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


  • 78
    public class Solution {
        public List<String> readBinaryWatch(int num) {
            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) {
                res.add(sum);
                return;
            }
            
            for(int i = pos; i < nums.length; i++) {
                generateDigitHelper(nums, count - 1, i + 1, sum + nums[i], res);    
            }
        }
    }
    

  • 35

    big god
    plz receive my knees


  • 2
    N

    @xietao0221 big shen, please receive my knees


  • 0
    S

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


  • 0
    M

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


  • 0
    J

    receive my knees


  • 0
    Y

    this is really good! I really need learn more


  • 2
    P

    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++) {
    

  • 1
    Y

    @pford You can also add the following after it:

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

  • 0
    W

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


  • 0
    W

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


  • 4
    J

    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.


  • 0
    Y

    what is the time complexity?


  • 0
    This post is deleted!

  • 0

    Thanks for sharing.


  • 2

    Similar ideas with you, easy to understand

    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> result = new ArrayList<>();
            if(num == 0){
                result.add("0:00");
                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;
                        result.add(temp);
                    }
                }
            }
    
            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){
                list.add(String.valueOf(curSum));
                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);
                list.add(temp);
                return;
            }
            for(int i = index; i < array.length; i++){
                curSum += array[i];
                minuteHelper(array, curSum, i+1, level+1, num, list);
                curSum -= array[i];
            }
        }
    }
    

  • 0
    J

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


  • 0
    S

    very helpful


  • 0

    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);
                }
            }
        }
    

  • 0
    B

    @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){
                timeList.add(sum);
            }
            while(max>=1){
                generateTime(count-1, sum+max, max>>>1, timeList);
                max = max >>> 1;
            }
        }
    

Log in to reply
 

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