LeetCode401. 二进制手表 （回溯法）

https://leetcode-cn.com/problems/binary-watch/

二进制手表顶部有 4 个 LED 代表小时（0-11），底部的 6 个 LED 代表分钟（0-59）。
每个 LED 代表一个 0 或 1，最低位在右侧。

例如，上面的二进制手表读取 “3:25”。

给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
案例:
输入: n = 1
返回: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]

注意事项:
输出的顺序没有要求。
小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”。
分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。

思路： 回溯算法（暴力穷举，验证是否为正确的时间）

/** * Return an array of size *returnSize. * Note: The returned array must be malloced, assume caller calls free(). */
void DFS(int index, int h, int m, int num, int *returnSize, char **ret){
    if(0 == num){
        if(h > 11 || m > 59){
            return;
        }
        ret[*returnSize] = (char *)calloc(100, sizeof(char));
        if(m < 10){
            snprintf(ret[*returnSize], 6, "%d:0%d", h, m);
        }else{
            snprintf(ret[*returnSize], 6, "%d:%d", h, m);
        }
        int len = strlen(ret[*returnSize]);
        ret[*returnSize][len] = '\0';
        *returnSize += 1;
    }
    int i = index;
    for(; i < 10; i++){
        if(i < 6){ // m
            m += pow(2, i);
            DFS(i + 1, h, m, num - 1, returnSize, ret);
            m -= pow(2, i);
        }else { // h
            h += pow(2, (i - 6));
            DFS(i + 1, h, m, num - 1, returnSize, ret);
            h -= pow(2, (i - 6));
        }
    }  
}

char** readBinaryWatch(int num, int* returnSize) {
    if(num < 0 || num > 8){
        *returnSize = 0;
        return NULL;
    }
    
    char **ret = (char **)calloc(1024, sizeof(char *));
    *returnSize = 0;
    
    DFS(0, 0, 0, num, returnSize, ret);
    return ret;
}