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.

本来就是一个很直接的backtracking，但是由于有个手表的场景设置，要做一些额外的check，比如小时数不能大于等于12，分钟数不能大于等60

class Solution {
    public List<String> readBinaryWatch(int num) {
        List<String> res = new ArrayList<String>();
        int[] cs = new int[10];
        helper(res, cs, 0, num);
        Collections.sort(res, new Comparator<String>() {
            public int compare(String s1, String s2) {
                String[] ss1 = s1.split(":");
                String[] ss2 = s2.split(":");

                if(Integer.parseInt(ss1[0]) > Integer.parseInt(ss2[0]))
                    return 1;
                if(Integer.parseInt(ss1[0]) < Integer.parseInt(ss2[0]))
                    return -1;

                if(Integer.parseInt(ss1[1]) > Integer.parseInt(ss2[1]))
                    return 1;
                if(Integer.parseInt(ss1[1]) < Integer.parseInt(ss2[1]))
                    return -1;

                return 0;
            }
        });
        return res;
    }

    public void helper(List<String> res, int[] cs, int start, int num) {
        if(num == 0) {
            String time = decode(cs);
            if(time.length() > 0)
                res.add(time);
            return;
        }

        if(start == cs.length)
            return;

        for(int i = start; i < cs.length; i++) {
            cs[i] = 1;
            helper(res, cs, i + 1, num - 1);
            cs[i] = 0;
        }
    }

    public String decode(int[] cs) {
        String hourStr = "";
        for(int i = 0 ; i < 4; i++)
            hourStr = hourStr + cs[i];

        int hour = Integer.parseInt(hourStr, 2);
        if(hour >= 12)
            return "";

        String minStr = "";
        for(int i = 4 ; i < 10; i++)
            minStr = minStr + cs[i];

        int min = Integer.parseInt(minStr, 2);
        if(min >= 60)
            return "";

        if(min < 10)
            return String.valueOf(hour) + ":0" + String.valueOf(min);
        else
            return String.valueOf(hour) + ":" + String.valueOf(min);
    }
}