401. 二进制手表

这里可以通过遍历的方式做出来。

i从0~1111111111进行遍历，如果1的个数等于要求的个数tournedOn，此时进一步判断时钟位和分钟为是否符合要求，满足要求则放入结果容器中。

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> res;
        char str[10];
        for(int i = 0; i < 1 << 10; i ++ ) {
            int s = 0; // 存储1的个数
            for(int j = 0; j < 10; j ++ ) {
                if(i >> j & 1) s ++;
            }
            if(s == turnedOn ) {
　　　　　　　　　　// a是时钟位，b是分钟位
                int a = i >> 6, b = i & 63;
　　　　　　　　　　// 判断a和b是否符合要求
                if(a < 12 && b < 60) {
                    sprintf(str, "%d:%02d", a, b);
                    res.push_back(str);
                }
            }
        }
        return res;
    }
};

虽然本题是简单题，但同样可以用回溯+剪枝来做

index迭代一定要+1，否则无法跳出

class Solution {
public:
　　// 这里定义的全局变量，但是同样可以通过局部变量+引用来传参
    vector<string> res;
　　// hours和minutes字符数组的值一定要是错开的！！！只有先确定hours才能去确定minutes
    char hours[10] = {1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
    char minutes[10] = {0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
    vector<string> readBinaryWatch(int turnedOn) {
        readOnce(turnedOn, 0, 0, 0);
        return res;
    }

    void readOnce(int turnedOn, int index, int hour, int minute) {
　　　　　　// 跳出迭代的条件
　　　　　if(hour > 11 | minute > 59) return;
　　　　　　// 如果是0， 则只有0：00
        if(turnedOn == 0) {
            char str[10];
            sprintf(str, "%d:%02d", hour, minute);
            res.push_back(str);
            return;
        }
　　　　// index就是需要遍历的字符数组的下标，从1开始到字符数组的size结束
　　　　// 注意，每次回溯，index需要+1，否则会陷入死循环
        for(int i = index; i < 10; i ++ ) {
            readOnce(turnedOn - 1, i + 1, hour + hours[i], minute + minutes[i]);
        }
    }
};

注意：由于计算和输入无关，因此时间复杂度O(1),唯一可以优化的是空间。

回溯+剪枝的空间虽然不理想，但是有助于理解回溯的思想。