401. Binary Watch

A binary watch has 4 LEDs on the top which represent thehours(0-11), and the 6 LEDs on the bottom represent theminutes(0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads "3:25".

Given a non-negative integernwhich represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1


Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

• The order of output does not matter.
• The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
• The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

Analysis:

Use recursion to find out combination of hours and minutes separately. Its like "choose x element from a array of length y" question, it usually just go with following recursion

for(int i = pos; i < arr.length; i++){

recursion\(pos + 1, arr, count -1, someValue + nums\[i\]\);

}

Complexity:

Time:

Space:

Code:

public class Solution {
    private int[] hour = new int[]{8,4,2,1};
    private int[] minute = new int[]{32,16,8,4,2,1};

    public List<String> readBinaryWatch(int num) {
        List<String> returnList = new LinkedList<String>();
        if (num > 8){
            return returnList;
        }
        int low = num-5 < 0 ? 0 : num-5;
        int high = num >= 3 ? 3 : num;

        for(int i = low; i <= high; i++){
            List<Integer> hours = possibleNum(hour, i);
            List<Integer> minutes = possibleNum(minute, num - i);
            for(Integer h : hours){
                if(h > 11) {
                    continue;
                }
                for(Integer m : minutes){
                    if(m > 59){
                        continue;
                    }
                    returnList.add(h.toString() + ":" + (m.intValue() >= 10 ? m.toString() : "0" + m.toString()));
                }

            }
        }
        return returnList;
    }

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

    private void possibleNum(int[] nums, int count, int pos, int sum, List<Integer> rtr){
        if(count == 0){
            rtr.add(sum);
            return;
        }

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