A FB challenge

fb_challenge.cpp

// Compile with C++ 17
#include <iostream>
#include <string>
#include <vector>
#include <tuple>
#include <cassert>

using namespace std;

typedef long long int64;

bool find(const string& digits, int64 target, int index) {
    if (index >= digits.length()) {
        return target == 0;
    }
    if (target == 0) {
        return true;
    }

    int value = 0;
    for (int i = index; i < digits.length(); i++) {
        value = value * 10 + digits[i] - '0';
        if (find(digits, target - value, i + 1) || find(digits, target + value, i + 1)) {
            return true;
        }
    }
    // Ignore the current digit
    return find(digits, target, index + 1);
}

bool find(const string& digits, int64 target) {
    return find(digits, target, 0);
}

int main() {
    vector<tuple<string, int64, bool>> testCases{
            make_tuple("5116175380243302935", 5116LL, true),
            make_tuple("5116175380243302935", 4766LL, true),
            make_tuple("5116175380243302935", 753802LL, true),
            make_tuple("5116175380243302935", 0LL, true),
            make_tuple("123", 15LL, true),
            make_tuple("123", 6LL, true),
            make_tuple("2637281563", 107935LL, true),
            make_tuple("2637281563", 99LL, true),
            make_tuple("2", 0, true),
            make_tuple("14", -3LL, true),
            make_tuple("505", -55LL, true),

            make_tuple("2637281563", 2637281564LL, false),
            make_tuple("00000100000", 2, false),
            make_tuple("00000000010", 100, false),
            make_tuple("001", 10, false),
            make_tuple("1", 2, false),
            make_tuple("222222222222", 1, false)
    };
    std::cout << std::boolalpha;
    for (const auto& testCase : testCases) {
        auto& [input, target, expected] = testCase;
        assert(find(input, target) == expected);
    }
    return 0;
}