leetcde-401(back-tracking).cpp

#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<int> hour = {1, 2, 4, 8}, minute = {1, 2, 4, 8, 16, 32};

void helper(vector<string>& res, pair<int, int> time, int num, int start_point) {
        if (num == 0) {
            res.push_back(to_string(time.first) +  (time.second < 10 ?  ":0" : ":") + to_string(time.second));
            return;
        }
        for (int i = start_point; i < hour.size() + minute.size(); i ++)
            if (i < hour.size()) {
                time.first += hour[i];
                if (time.first < 12)     helper(res, time, num - 1, i + 1);     // "hour" should be less than 12.
                time.first -= hour[i];
            } else {
                time.second += minute[i - hour.size()];
                if (time.second < 60)    helper(res, time, num - 1, i + 1);     // "minute" should be less than 60.
                time.second -= minute[i - hour.size()];
            }
    }

    int main()
    {
      vector<string> res;
      helper(res,make_pair(0,0),3,0);
      for(auto s:res)
        cout<<s<<endl;
      return 0;
    }