• Array
  • Generate Subbarray
  • Unique Pair
• Big Integers
  • Addition
• Bit Masking
  • Arithmetic
  • Bit Operation
  • Even Odd
  • Power
  • Swap
• Graph
  • Combinatorics
    • Binomial Coeefficient
    • Birthday Paradox
    • Catalan Number
    • Number of digit in factorial
    • Zero at end of factorial
  • Prime
    • Is Prime
    • Prime Factorization
    • Segmented Sieve
    • Sieve of Eratosthenes
  • Chinese Remainder
  • Divisors
  • Euler Totient
  • Exponentiation
  • Euclidean
  • Extended Euclidean
  • Matrix Exponentiation
  • Modulo Arithmetic
  • Fast Multiplication
  • MMI
• Number Theory
  • Shortestpath BFS
• Searching
  • Lower-Upper Bound
• Sorting
  • Inversion Count
  • Is Sorted

• Recursion

  • Forward Recursion
  • Backward Recursion
  • How Recursion Uses the Stack
    • Understaing Call Stack Behavior
    • Tree Recursion
    • Tracing Tree

• Subsequence

  • Subsequence vs Substring
  • Recursive Approach
  • Iterative Approach

• Overflow Underflow

  • How to avoid overflow and underflow

• Bit Manipulation

• Even Odd

• Time Limit

• Sum

• Reverse VS Sort

• Binary Search

The recursive calls happen first, and any operations are performed after all recursive calls have returned.

void forwardRecursion(int n) {
    if (n == 0) {
        return;
    }
    forwardRecursion(n - 1);
    cout << n << " ";
}
// 1 2 3 4 5 6 7 8 9 10

The operations are performed before the recursive calls. Each recursive call processes its action and then makes the next recursive call.

void backwardRecursion(int n) {
    if (n == 0) {
        return;
    }
    cout << n << " ";
    backwardRecursion(n - 1);
}
// 10 9 8 7 6 5 4 3 2 1

In recursion, each function call is pushed onto the stack. When a function finishes, it's popped off the stack, and execution returns to the previous function call.

1. Function Call: Each recursive call adds a new frame to the stack, containing:

- Local variables
- Parameters
- Return address (where to resume after the function ends)

2. Base Case: When the base case is hit, the recursion stops — the function returns, and the stack starts unwinding.

3. Stack Unwinding: As each function returns, its frame is popped off the stack, and the result is passed back to the previous frame.

For sum of N integer, suppose you input num = 3. The recursive function works like this:

1. sum(3) is called → Push sum(3) onto the stack
2. sum(2) is called → Push sum(2) onto the stack
3. sum(1) is called → Push sum(1) onto the stack
4. sum(0) is called → Push sum(0) onto the stack At this point, the stack looks like this:

| sum(0) |
| sum(1) |
| sum(2) |
| sum(3) |   <-- Top of the stack

🛑 Base Case Reached:

• sum(0) returns 0, and the stack starts unwinding.

🔓 Stack Unwinding:

• sum(1) pops from the stack and returns 1.
• sum(2) pops from the stack and returns 2 + 1 = 3.
• sum(3) pops from the stack and returns 3 + 3 = 6.

A function makes more than one recursive call to itself. This creates a recursive tree-like structure where each function call branches into multiple sub-calls.

Optimize Tree Recursion:

• Memoization
• Tabulation
• Iteration

Forward Recursion:

                      forwardPrint(3)
                            |
                    forwardPrint(2)
                            |
                    forwardPrint(1)
                            |
                    forwardPrint(0)  <- Base case
                            |
                          Print(1)
                            |
                          Print(2)
                            |
                          Print(3)

Backward Recursion:

                      backwardPrint(3)
                            |
                         Print(3)
                            |
                    backwardPrint(2)
                            |
                         Print(2)
                            |
                    backwardPrint(1)
                            |
                         Print(1)
                            |
                    backwardPrint(0) <- Base case

A subsequence of a sequence (string, array, list, etc.) is a sequence that can be derived from the original sequence by deleting zero or more elements without changing the relative order of the remaining elements.

• Elements must preserve order (cannot rearrange).
• You may delete some elements or none at all.

Example

• All possible subsequences of A = [3, 1, 2] is [] (empty subsequence – always included), [3], [1], [2], [3, 1], [3, 2], [1, 2], [3, 1, 2]
• All Possible subsequence of abc is "" (empty string) "a", "b", "c", "ab", "ac", "bc", "abc"
• Total subsequences = 2^n (where n = length of sequence).

Applications of Subsequences in DSA

• Longest Common Subsequence (LCS) – used in diff tools, DNA sequencing, spell checkers.
• Longest Increasing Subsequence (LIS) – used in dynamic programming problems.
• Subsequence Sum Problems – like subset sum, knapsack problem.
• String Matching – checking if one string is a subsequence of another.

• Substring: Continuous part of the string/array.
  • "ab" is a substring of "abc".
  • "ac" not a substring (because not continuous).
• Subsequence: Not necessarily continuous, but order must be preserved.
  • "ac" is a subsequence of "abc".

For a sequence s of length n, at index i you always have two choices:

1. Exclude s[i] from the current subsequence
2. Include s[i] in the current subsequence

Exploring both choices at every index creates a full binary recursion tree with 2^n leaves (each leaf = one subsequence) with height n = s.size()

Recursion Tree:

                         i=0, path=""
                    /                         \
            exclude 'a'                    include 'a'
            i=1, ""                        i=1, "a"
            /       \                      /         \
      excl 'b'   incl 'b'            excl 'b'     incl 'b'
      i=2,""     i=2,"b"             i=2,"a"      i=2,"ab"
       /  \        /  \                /   \         /   \
   ""  "c"     "b"  "bc"           "a"   "ac"    "ab"   "abc"

Code Implementation:

#include <bits/stdc++.h>
using namespace std;

void generateSubsequences(string s, string current, int index) {
    if (index == s.size()) {
        cout << "\"" << current << "\"" << endl; // print subsequence
        return;
    }

    // Choice 1: Exclude current character
    generateSubsequences(s, current, index + 1);

    // Choice 2: Include current character
    generateSubsequences(s, current + s[index], index + 1);
}

int main() {
    string s = "abc";
    cout << "All subsequences of \"" << s << "\":" << endl;
    generateSubsequences(s, "", 0);
    return 0;
}

1. Base case: if (index == s.size()) — we've decided for every character; current is a complete subsequence → print and return.

2. Exclude branch: call the function with index+1 but do not change current.

3. Include branch: call with current + s[index] and index+1 — this appends the current character to the subsequence.

Because you do exclude first then include, the printed order follows that traversal (empty subsequence first, then subsequences that include later characters first, etc.).

Call Trace:

Root: (0, "")

• Exclude a → (1, "")
  • Exclude b → (2, "")
    • Exclude c → (3, "") print ""`
    • Include c → (3, "c") print "c"`
  • Include b → (2, "b")
    • Exclude c → (3, "b") print "b"`
    • Include c → (3, "bc") print "bc"`
• Include a → (1, "a")
  • Exclude b → (2, "a")
    • Exclude c → (3, "a") print "a"`
    • Include c → (3, "ac") print "ac"`
  • Include b → (2, "ab")
    • Exclude c → (3, "ab") print "ab"
    • Include c → (3, "abc") print "abc"

""
"c"
"b"
"bc"
"a"
"ac"
"ab"
"abc"

Optimized recursive version (avoid copies)

Two small changes yield much better performance:

• Pass s as const string& (no copying).
• Keep current as a single string passed by reference and push/pop characters (backtracking) — avoids making a new string at every call.

#include <bits/stdc++.h>
using namespace std;

void generateSubsequences(const string &s, string &current, int index) {
    if (index == (int)s.size()) {
        cout << "\"" << current << "\"\n";
        return;
    }

    // Exclude s[index]
    generateSubsequences(s, current, index + 1);

    // Include s[index]
    current.push_back(s[index]);
    generateSubsequences(s, current, index + 1);
    current.pop_back(); // backtrack
}

int main() {
    string s = "abc";
    string cur = "";
    cout << "All subsequences of \"" << s << "\":" << endl;
    generateSubsequences(s, cur, 0);
    return 0;
}

Why this is better:

• s is never copied.
• current.push_back() and pop_back() mutate a single buffer; no O(n) copies per recursive call.
• Time becomes closer to O(2^n + total_output_size) (still exponential because of output), and memory usage is minimal (stack depth O(n) and current length <= n).

Time Complexity: O(n * 2^n)

• At each index, we make two recursive calls → one for including, one for excluding.
• So total calls = 2^n.
• For each subsequence, printing takes O(n) in the worst case (when subsequence length ≈ n).

Space Complexity = O(n)

• Maximum depth of recursion = n (stack space).
• Space used for storing subsequences (if printing immediately, not storing all) = O(n).

Since there are 2^n subsequences, we can represent each subsequence using a binary mask:

• 0 → exclude character
• 1 → include character

Example:

For "abc" → length = 3 → total subsequences = 2^3 = 8

• 000 → ""
• 001 → "c"
• 010 → "b"
• 011 → "bc"
• 100 → "a"
• 101 → "ac"
• 110 → "ab"
• 111 → "abc"

Code Implementation:

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s = "abc";
    int n = s.size();
    int total = 1 << n; // 2^n subsequences

    cout << "All subsequences of \"" << s << "\":" << endl;

    for (int mask = 0; mask < total; mask++) {
        string subseq = "";
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) { // if bit is set, include s[i]
                subseq += s[i];
            }
        }
        cout << "\"" << subseq << "\"" << endl;
    }
    return 0;
}

Time Complexity: O(n * 2^n) (same as recursion).

• We loop over all 2^n bitmasks.
• For each mask, we check up to n bits → O(n).

Space Complexity: O(n)

• No recursion stack.
• Only needs a string to build subsequence at each iteration.

1. Longest Common Subsequence
2. Longest Common Subsequence – LeetCode
3. Longest Common Subsequence – WorkAtTech
4. Printing Longest Common Subsequence
5. Print all LCS sequences

1. Longest Increasing Subsequence – GeeksforGeeks
2. Longest Increasing Subsequence – LeetCode
3. Longest Increasing Subsequence – WorkAtTech
4. Longest Increasing Subsequence Size (N log N)
5. Print Longest Increasing Subsequence

1. Check if one string is subsequence of other
2. Check for subsequence
3. Check if a String is Subsequence of Other

1. Competitive programming: Good Subsets problem
2. Longest Common Increasing Subsequence (LCS + LIS)
3. Length of the Longest Subsequence That Sums to Target
4. Longest Subsequence With Limited Sum
5. Largest Divisible Subset
6. Longest Common Subsequence Between Sorted Arrays
7. Find the Longest Common Subsequence (LCS) in given K permutations

Overflow occurs when a variable is assigned a value greater than its maximum limit, causing the value to wrap around and produce incorrect results.

• An int is typically 32 bits, so it can store values between -2^31 and 2^31 - 1 (i.e., -2147483648 to 2147483647).

If you assign a value larger than 2147483647 to an int, overflow will occur. For example:

int x = INT_MAX;
cout << "Before overflow: " << x << endl;
x = x + 1;
cout << "After overflow: " << x << endl;

Here, adding 1 to 2147483647 causes the variable to wrap around to the minimum value -2147483648.

Underflow does the same but in the opposite direction.

1. Use larger data types: consider data types with larger ranges, such as long long
2. Check for overflow/underflow conditions manually:

if(x > INT_MAX){
    // Handle overflow case
}

3. Modular arithmatic: you can use modulo 10^9+7 as a limit to avoid overflow.

The bit at position 0 represents the least significant bit (LSB), and the bit at position n−1 represents the most significant bit (MSB).

int number = 5;
bool isBitSet = (number & (1 << 0)) != 0;

The bit at position 1 represents the least significant bit, and the bit at position n represents the most significant bit.

int number = 5;
bool isBitSet = (number & (1 << (1 - 1))) != 0;

• count the number of even number between range [a, b]: $$ \left\lfloor \frac{b}{2} \right\rfloor - \left\lfloor \frac{a-1}{2} \right\rfloor $$ count the number of odd number between range [a, b]: $$ (b - a + 1) - \left( \left\lfloor \frac{b}{2} \right\rfloor - \left\lfloor \frac{a-1}{2} \right\rfloor \right) $$
• $$ {even}^{even}={even} $$
• $$ {odd}^{odd}={odd} $$
• $$ {even}+{even}={even} $$
• $$ {odd}+{odd}={even} $$
• $$ {even}+{odd}={odd} $$

• sum of integers in the range [a,b]: $$ \frac{b-a+1}{2} \times (a + b) $$

• time complexity is O(n)
• doesn't consider the original order

• time complexity is O(nlogn)
• changes order based on sorting criteria

1. Sort the array
2. Define search space
3. Handle corner cases
4. Conditional Check
5. Function building
6. Update search space
7. Extract solution