Binary Watch Solutions in C++

// Source : https://leetcode.com/problems/binary-watch/
// Author : Hao Chen
// Date   : 2016-11-05



class Solution {
private:
    void combination(int nLED, int nLight, int max, bool zero,
                     int start, int k, int solution, 
                     vector<vector<string>>& result) {
        if (solution > max){
            return;
        }
        if (k == 0) {
            char tmp[5] = "";
            if (zero) {
                sprintf(tmp, "%02d", solution);
            }else{
                sprintf(tmp, "%d", solution);
            }
            result[nLight].push_back(tmp);
            return;
        }
        for (int i=start; i<=nLED-k; i++) {
            solution += pow(2, i);
            combination(nLED, nLight, max, zero, i+1, k-1, solution, result);
            solution -= pow(2, i);
        }
    }
    
    void generate_combination(int nLED, int max, bool zero, vector<vector<string>>& result) {
        for (int i=0; i<nLED; i++) {
            combination(nLED, i, max, zero, 0, i, 0, result);
        }
    }
    
    void print(vector<vector<string>>&  vv) {
        for(auto v : vv) {
            cout << "[ ";
            for (auto i : v) {
                cout << i << " ";
            }
            cout << "]" << endl;
        }
    }
    
private:
    vector<vector<string>> hour;
    vector<vector<string>> mins;

public:

    Solution():hour(4, vector<string>()), mins(6, vector<string>()){
        generate_combination(4, 11, false, hour);
        //print(hour);
        //[ 0 ]
        //[ 1 2 4 8 ]
        //[ 3 5 9 6 10 ]
        //[ 7 11 ]
        
        
        generate_combination(6, 59, true, mins);
        //print(mins);
        //[ 00 ]
        //[ 01 02 04 08 16 32 ]
        //[ 03 05 09 17 33 06 10 18 34 12 20 36 24 40 48 ]
        //[ 07 11 19 35 13 21 37 25 41 49 14 22 38 26 42 50 28 44 52 56 ]
        //[ 15 23 39 27 43 51 29 45 53 57 30 46 54 58 ]
        //[ 31 47 55 59 ]        
    }
    
    vector<string> readBinaryWatch(int num) {
        
        vector<string> result;
        for (int i = 0; i <= 3 && i <= num; i++) {
            if (num - i > 5) {
                continue;
            }
            for (auto h : hour[i]) {
                for (auto m : mins[num - i]) {
                    result.push_back( h + ":" + m );
                }
            }
            
        }
        return result;
    }
};

/// Source : https://leetcode.com/problems/binary-watch/
/// Author : liuyubobobo
/// Time   : 2020-02-15

#include <iostream>
#include <vector>
#include <sstream>
#include <iomanip>

using namespace std;


/// Brute Force
/// Time Complexity: O(2^10)
/// Space Complexity: O(1)
class Solution {

public:
    vector<string> readBinaryWatch(int num) {

        vector<string> res;
        for(int i = 0; i < (1 << 10); i ++)
            if(num_of_ones(i) == num){
                int m = i & 0b111111, h = i >> 6;
                if(h < 12 && m < 60){
                    stringstream ss;
                    ss << h << ":" << setfill('0') << setw(2) << m;
                    res.push_back(ss.str());
                }
            }
        return res;
    }

private:
    int num_of_ones(int x){
        int res = 0;
        while(x) res += x % 2, x /= 2;
        return res;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/binary-watch/
/// Author : liuyubobobo
/// Time   : 2020-02-15

#include <iostream>
#include <vector>
#include <sstream>
#include <iomanip>

using namespace std;


/// Backtracking
/// Time Complexity: O(2^10)
/// Space Complexity: O(1)
class Solution {

public:
    vector<string> readBinaryWatch(int num) {

        vector<string> res;
        vector<bool> bits(10, false);
        go(bits, 0, num, res);
        return res;
    }

private:
    void go(vector<bool>& bits, int index, int num, vector<string>& res){

        if(index == 10){
            int h = 0;
            for(int i = 0; i < 4; i ++) h = h * 2 + bits[i];

            int m = 0;
            for(int i = 4; i < 10; i ++) m = m * 2 + bits[i];

            if(h < 12 && m < 60){
                stringstream ss;
                ss << h << ":" << setfill('0') << setw(2) << m;
                res.push_back(ss.str());
            }

            return;
        }

        if(10 - index > num) go(bits, index + 1, num, res);
        if(num){
            bits[index] = true;
            go(bits, index + 1, num - 1, res);
            bits[index] = false;
        }
        return;
    }
};


int main() {

    return 0;
}