0ms c++ recursive solution


  • 0
    I
    bool help(long *prev1, long *prev2, int start, string& num) {
        if (!prev1) {
            for (int i = 1; i <= num.size() / 2; i++) {
                long temp = stol(num.substr(0, i));
                if (help(&temp, NULL, i, num)) return true;
                if (temp == 0) break;
            }
            return false;
        } else if (!prev2) {
            for (int i = 1; i <= (num.size() - start) / 2; i++) {
                long temp = stol(num.substr(start, i));
                if (help(prev1, &temp, start + i, num)) return true;
                if (temp == 0) break;
            }
            return false;
        } else {
            for (int i = 1; start + i <= num.size(); i++) {
                long temp = stol(num.substr(start, i));
                if (temp == (*prev1) + (*prev2)) {
                    if (start + i == num.size()) {
                        return true;
                    } else {
                        if (help(prev2, &temp, start + i, num)) return true;
                    }
                }
                if (temp == 0) break;
            }
            return false;
        }
    }
    
    bool isAdditiveNumber(string num) {
        return help(NULL, NULL, 0, num);
    }

Log in to reply
 

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