Paste_Image.png

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 = 1Return: ["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:

参考 discuss 得出以下解法：
利用 dfs 来枚举所有情况，将当前已经有的 "1" 的个数当参数传入每一次递归调用。每次递归先检查当前"1"的个数是否已经足够，如果足够就进行“验证并保存有效结果”。然后再进行数组index 是否越界的判断，如果越界则 return（千万不能先判断，因为每次调用子递归的时候都将 index+1再传入子递归，而父递归“1”的个数是否足够是在子递归里面判断的。如果父递归将最后一位置“1” 后 “1”的个数正好达标，将index+1后越界，则这种情况因为在子递归中提前判断越界而遗漏掉了……）

怎么觉得这题这么难……惊了，智商被狗吃了……

import java.util.ArrayList;
import java.util.List;

public class Solution
{
    public List<String> readBinaryWatch(int num)
    {
        result = new ArrayList<>();
        boolean[] a = new boolean[10];
        dfs(a, num, 0, 0);
        return result;
    }

    public List<String> result;
    public int[] clock = new int[]{8, 4, 2, 1, 32, 16, 8, 4, 2, 1};

    /*
     * num is target number of 1.
     * index is current index of bit
     * k is current number of 1
     */
    public void dfs(boolean[] a, int num, int index, int k)
    {
        /*
        // below if block cannot put here!!! It must go after "if (k == num)" block
        if(index >= a.length)
            return;
        */

        // if we now have enough number of 1
        if(k == num)
        {
            int hour = 0, min = 0;
            for(int i = 0; i < a.length; i++)
            {
                if(a[i] == true)
                {
                    if(i < 4)
                        hour += clock[i];
                    else
                        min += clock[i];
                }
            }
            if(hour < 12 && min < 60)
            {
                if (min < 10)
                    result.add("" + hour + ":" + "0" + min);
                else
                    result.add("" + hour + ":" + min);
            }
            return;
        }
        
        // THIS IS THE RIGHT PLACE!!!!!!!!
        if(index >= a.length)
            return;
        
        else
        {
            a[index] = true;
            dfs(a, num, index + 1, k + 1);

            a[index] = false;
            dfs(a, num, index + 1, k);
        }
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        System.out.println(solution.readBinaryWatch(1));
    }

}