// Reverse an array using recursion
void reverseArr(vector<int>& a, int l, int r) {
    if (l >= r) return;
    swap(a[l], a[r]);
    reverseArr(a, l + 1, r - 1);
}

// Check palindrome recursively
bool isPalin(string& s, int l, int r) {
    if (l >= r) return true;
    if (s[l] != s[r]) return false;
    return isPalin(s, l+1, r-1);
}

// Count digits in a number
int countDigits(int n) {
    if (n == 0) return 0;
    return 1 + countDigits(n / 10);
}

void merge(vector<int>& a, int l, int m, int r) {
    vector<int> tmp;
    int i = l, j = m + 1;
    while (i <= m && j <= r)
        tmp.push_back(a[i] <= a[j] ? a[i++] : a[j++]);
    while (i <= m) tmp.push_back(a[i++]);
    while (j <= r) tmp.push_back(a[j++]);
    for (int k = l; k <= r; k++) a[k] = tmp[k-l];
}

void mergeSort(vector<int>& a, int l, int r) {
    if (l >= r) return;           // base case
    int m = l + (r - l) / 2;
    mergeSort(a, l, m);            // left half
    mergeSort(a, m+1, r);         // right half
    merge(a, l, m, r);             // combine
}
// Time: O(n log n) | Space: O(n)

void subsets(vector<int>& nums, int idx,
             vector<int>& cur, vector<vector<int>>& res) {
    if (idx == nums.size()) {
        res.push_back(cur);  // base: record subset
        return;
    }
    // PICK nums[idx]
    cur.push_back(nums[idx]);
    subsets(nums, idx + 1, cur, res);

    // NOT PICK nums[idx] (backtrack)
    cur.pop_back();
    subsets(nums, idx + 1, cur, res);
}
// For [1,2,3] generates 2³ = 8 subsets
// [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]

void permute(vector<int>& nums, int start,
             vector<vector<int>>& res) {
    if (start == nums.size()) {
        res.push_back(nums); return;
    }
    for (int i = start; i < (int)nums.size(); i++) {
        swap(nums[start], nums[i]);   // CHOOSE
        permute(nums, start+1, res);  // EXPLORE
        swap(nums[start], nums[i]);   // UNDO (backtrack)
    }
}

// Combination Sum — pick same element multiple times
void combSum(vector<int>& cands, int target, int idx,
             vector<int>& cur, vector<vector<int>>& res) {
    if (target == 0) { res.push_back(cur); return; }
    if (idx == cands.size() || target < 0) return;
    cur.push_back(cands[idx]);
    combSum(cands, target-cands[idx], idx, cur, res); // reuse
    cur.pop_back();
    combSum(cands, target, idx+1, cur, res);          // skip
}

struct Node { int val; Node*left, *right; };

void inorder(Node* root) {        // Left Root Right
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

void preorder(Node* root) {       // Root Left Right
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

int height(Node* root) {           // DFS to find depth
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}

// Sum array elements recursively
int arrSum(vector<int>& a, int i) {
    if (i == a.size()) return 0;
    return a[i] + arrSum(a, i + 1);
}

// Reverse a string
string revStr(string s, int i) {
    if (i == s.size()) return "";
    return revStr(s, i+1) + s[i]; // head recursion!
}

// Find max in array
int arrMax(vector<int>& a, int i) {
    if (i == (int)a.size() - 1) return a[i];
    return max(a[i], arrMax(a, i + 1));
}

unordered_map<int,int> memo;

int fib(int n) {
    if (n <= 1) return n;
    if (memo.count(n)) return memo[n]; // cache hit!
    memo[n] = fib(n-1) + fib(n-2);   // store result
    return memo[n];
}
// Time: O(n) | Space: O(n) — huge improvement!

// Cleaner with vector
int fibMemo(int n, vector<int>& dp) {
    if (n <= 1) return n;
    if (dp[n] != -1) return dp[n];
    return dp[n] = fibMemo(n-1,dp) + fibMemo(n-2,dp);
}
// Call: vector<int> dp(n+1,-1); fibMemo(n, dp);