问题：
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".
解决：
【注】
关于回溯法：
① 使用回溯的思想，分别在小时和分钟上做DFS（DFS可以看作是回溯的一种），给定几个灯亮，然后把这些亮的灯枚举分给小时和分钟．需要注意的是剪枝，即小时必须小于１２，分钟小于６０．然后将小时和分钟组合即可．还有一个需要注意的是如果分钟只有１位数，还要补０。
public class Solution { // 3ms
public List<String> readBinaryWatch(int num) { List<String> res = new ArrayList<>(); for (int i = Math.max(0,num - 6);i <= Math.min(4,num) ;i ++ ) { List<Integer> list1 = new ArrayList<>(); List<Integer> list2 = new ArrayList<>(); DFS(4,i,0,0,list1); DFS(6,num - i,0,0,list2); for (int n1 : list1) { for (int n2 : list2) { String str = (String.valueOf(n2).length() == 1 ? "0" : "") + String.valueOf(n2); res.add(String.valueOf(n1) + ":" + str); } } } return res; } public void DFS(int len,int k,int curIndex,int val,List<Integer> list){ if(k == 0 && len == 4 && val < 12) list.add(val); if(k == 0 && len == 6 && val < 60) list.add(val); if(curIndex == len || k == 0) return; //停止条件 DFS(len,k,curIndex + 1,val,list); val += Math.pow(2,curIndex);//计算第curIndex代表的值 k --; curIndex ++; DFS(len,k,curIndex,val,list); // } }② 在discuss中看到，将所有的小时和分钟的可能性用数组列出来，以空间换时间，耗时少。
public class Solution { //2ms
String[][] hour = { {"0"}, // hours contains 0 1's {"1", "2", "4", "8"}, // hours contains 1 1's {"3", "5", "6", "9", "10"}, // hours contains 2 1's {"7", "11"}}; // hours contains 3 1's String[][] minute = { {"00"}, // mins contains 0 1's {"01", "02", "04", "08", "16", "32"}, // mins contains 1 1's {"03", "05", "06", "09", "10", "12", "17", "18", "20", "24", "33", "34", "36", "40", "48"}, // mins contains 2 1's {"07", "11", "13", "14", "19", "21", "22", "25", "26", "28", "35", "37", "38", "41", "42", "44", "49", "50", "52", "56"}, // mins contains 3 1's {"15", "23", "27", "29", "30", "39", "43", "45", "46", "51", "53", "54", "57", "58"}, // mins contains 4 1's {"31", "47", "55", "59"}}; // mins contains 5 1's public List<String> readBinaryWatch(int num) { List<String> res = new ArrayList(); // loop from 0 to 3 which is the max number of bits can be set in hours (4 bits) for (int i = 0; i <= 3 && i <= num; i++) { // this if condition is to make sure the index from minutes array would be valid if (num - i <= 5) { // if we have i 1's in hours, then we need num - i 1's in minutes, that's why the arrays were created by grouping the number of 1's bits for (String str1 : hour[i]) { for (String str2 : minute[num - i]) { res.add(str1 + ":" + str2); } } } } return res; } }③ 使用Bit Manipulation来解决，1，2，4，8都是2的整数倍，它们的二进制都只包含一个1，所以搜索所有的解空间，看哪几个数的bit之和等于num。使用Integer.bitCount()来计算1的个数，这个方法既好理解，又好使用。
public class Solution { // 3ms
public List<String> readBinaryWatch(int num) { List<String> res = new ArrayList<>(); for (int h = 0;h < 12 ;h ++ ) { for (int m = 0;m < 60 ;m ++ ) { if(Integer.bitCount(h) + Integer.bitCount(m) == num){ String str1 = Integer.toString(h); String str2 = Integer.toString(m); res.add(str1 + ":" + (m < 10 ? "0" + str2 : str2)); } } } return res; } }