A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (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 integer n which 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".

Solution

public class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> ans = new ArrayList<String>();
        if(num < 0 || num > 10) return ans;
        for(int hourLight = 0; hourLight <= num; hourLight++) {
            int minuteLight = num - hourLight;

            List<Integer> hours = searchCombination(hourLight);
            List<Integer> minutes = searchCombination(minuteLight);

            for(Integer h: hours) {
                if(h < 12) {
                    for(Integer m: minutes) {
                        if(m < 60) {
                            if(m < 10) {
                                ans.add(h + ":0" + m);
                            } else {
                                ans.add(h + ":" + m);
                            }
                        }
                    }
                }
            }

        }

        return ans;
    }

    List<Integer> searchCombination(int num) {
        List<Integer> ans = new ArrayList<Integer>();
        backtracking(ans, 0, num, 0);
        return ans;
    }

    public int[] candidate = {1, 2, 4, 8, 16, 32};
    public void backtracking(List<Integer> ans, int curSum, int neededNum, int minIndex) {
        if(neededNum == 0) {
            ans.add(curSum);
            return;
        }

        // still need number but no ways to get
        if(minIndex >= candidate.length) return;

        for(int i = minIndex; i < candidate.length; i++) {
            backtracking(ans, curSum + candidate[i], neededNum - 1, i + 1);
        }

    }
}