C++ Backtracking and simple explanation


  • 0

    The backtracking method is very similar to solution to combination. Given 4 LEDs for hours and 6 LEDs for minutes, we can treat them as 10 separate buckets, and we are trying to find all the possible ways to throw n balls into them. For each way we use the results in the first 6 buckets to construct minute number and the last 4 buckets to construct hour number.

    Code:

    class Solution {
    public:
        vector<string> readBinaryWatch(int num) {
            vector<string> result;
            vector<int> path;
            combinations(10, num, 0, 0, path, result);
            return result;
        }
    
        void combinations(int n, int k, int start, int num, vector<int>& path, vector<string>& result) {
            if (num == k) {
                int hours = 0, minutes = 0;
                for (int ele : path) {
                    if (ele < 6)
                        minutes += pow(2, ele);
                    else
                        hours += pow(2, ele - 6);
                }
                if (hours < 12 && minutes < 60) {
                    string time = to_string(hours) + ':' + (minutes < 10 ? '0' + to_string(minutes) : to_string(minutes));
                    result.push_back(time);
                }
                return;
    
            }
            for (int i = start; i < n; i++) {
                path.push_back(i);
                combinations(n, k, i+1, num+1, path, result);
                path.pop_back();
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.