Problem

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 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".

思路一（dfs）

• 实际上是个组合问题， 首先从4个和32个之中选取1个亮灯， 那么之后就在3个和32个继续， 或者4个和31个之中继续
• 所以需要定义4个变量， 记录h的和， m的和，hours数组的指针，mins数组的指针
• 存在一个问题， 就是会出现重复的组合，
  • 原因是4个和32个中选取一个后，即下面两个子问题存在重复组合。 具体点就是选取A后的3和32 以及选取a后的4和31， 会出现【A, a】和【a, A】产生同样的数字
    • 4 + 31
    • 3 + 32
  • 解决， 采用hashset

    public List<String> readBinaryWatch(int num) {
        int[] hours = {1, 2, 4, 8};
        int[] mins = {1, 2, 4, 8, 16, 32};

        Set<String> result = new HashSet<>();

        helper(result, num, 0, 0, 0, 0, hours, mins);

        return new ArrayList<String>(result);
    }

    private void helper(Set<String> result, int num, int h, int m, int hi, int mi, int[] hours, int[] mins) {

        if (h > 11 || m > 59) return;
        if (num <= 0) {
            result.add(h + ":" + (m / 10 == 0 ? ("0" + m) : m));
            return;
        }
        for (int i = hi; i < hours.length; i++) {
            helper(result, num - 1, h + hours[i], m, i + 1, mi, hours, mins);
        }
        for (int i = mi; i < mins.length; i++) {
            helper(result, num - 1, h, m + mins[i], hi, i + 1, hours, mins);
        }
    }

思路二（循环 + Integer.bitCount(num)）

• 从1到11， 1到31循环组合， 每个组合的bit个数符合target即可

    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                if (Integer.bitCount(i) + Integer.bitCount(j) == num) {
                    res.add(String.format("%d:%02d", i, j));
                }
            }
        }
        return res;
    }