30 Day Challenge Day 13 | Leetcode 401. Binary Watch

题解

Easy | Backtracking/DFS

这道题被标记为Easy级别，可是我感觉并不简单，还是花了一些时间的。

class Solution {
public:
    vector<string> readBinaryWatch(int num) {    
        set<string> ret;
        vector<int> cur(10, 0);
        helper(num, 0, cur, ret);
        return vector<string>(ret.begin(), ret.end());
    }
    
    string parseTime(vector<int>& time) {
        int hour = 0, minute = 0;

        for(int i = 0; i < 4; i++) {
            if(time[i]) hour += pow(2, i);
        }

        for(int i = 4; i < 10; i++) {
            if(time[i]) minute += pow(2, i-4);
        }

        if(hour > 11 || minute > 59) return "";

        string h = to_string(hour);
        string m = minute > 9 ? to_string(minute) : '0' + to_string(minute);

        return h + ":" +  m;
    }
    
    void helper(int remain, int pos, vector<int>& cur, set<string>& ret) {
        if(remain == 0) {
            string time = parseTime(cur);
            if(time != "") ret.insert(time);
            return;
        }

        for(int i = pos; i < 10; i++) {
            if(cur[i] == 0) {
                cur[i] = 1;
                helper(remain-1, i, cur, ret);
                cur[i] = 0;
            }
        }


    }
};