📖 Complete Recursion Notes (Java + DSA

Focus)
📌 What is Recursion?
Recursion is a technique where a method calls itself to solve a smaller instance of the same problem.

Key components:

●​ Base case → condition to stop recursion

●​ Recursive case → function calling itself with a reduced problem

📌 Structure of a Recursive Function

void recursiveFunction(parameters) {
if (baseCondition) {
return; // stopping condition
}
// do something
recursiveFunction(smallerProblem); // recursive call
}

📌 How Recursion Works Internally

●​ Every function call is pushed onto the call stack
●​ When a base case is hit, it starts unwinding the stack
●​ Each call waits for its recursive call to finish

📌 Types of Recursion
Type Example / Use

Direct Recursion A function calls itself directly

Indirect Recursion Function A calls Function B, and B calls A

Tail Recursion Recursive call is the last operation in the function

Head Recursion Recursive call happens before any operation

Tree Recursion Function makes multiple recursive calls

📌 Important Recursion Patterns

✅ Backtracking​
✅ Divide & Conquer​
✅ Recursion with Memoization​
✅ Subset / Subsequence Generation​
✅ Tree / Graph Traversals​
✅ Dynamic Programming​
✅ Permutations / Combinations​
✅ Path Problems (Grid, Maze)
📌 Recursion Use Cases in DSA
 ●​ Factorial, Fibonacci
●​ Linked List (reverse, length, search)
●​ Tree Traversals (Pre, In, Post)
●​ Subset / Permutation generation
●​ Solving Maze / N-Queens
●​ Tower of Hanoi
●​ String manipulation
●​ Sorting (Merge Sort, Quick Sort)

📌 Base Condition (Why It’s Critical)

A recursion must have a base case to avoid stack overflow​
e.g.

if (n == 0) return;

📌 Recursion vs Iteration
Feature Recursion Iteration

Uses call stack Yes No

Base case needed Yes No

More memory usage Higher (stack) Less

Performance Sometimes Faster generally

slower

Easy for problems like Tree traversals Loops / simple problems

📌 Pros & Cons

✅ Pros
●​ Clean, elegant code
●​ Great for hierarchical problems (trees, graphs)
●​ Natural fit for Divide & Conquer

❌ Cons
●​ Risk of Stack Overflow
●​ More memory usage due to function call stack
●​ Can be slower if not optimized (use Memoization)

📌 Factorial Example
Iterative

int factorial(int n) {

int result = 1;
for (int i = 1; i <= n; i++) {
result *= i;
}
return result;
}

Recursive
int factorial(int n) {
if (n == 0) return 1; // base case
return n * factorial(n - 1);
}

📌 Fibonacci Example
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}

➡️ Time Complexity: O(2^N)​

➡️ Can optimize using Memoization (DP)
📌 Recursion Tree Visualization
For understanding recursion, draw a recursion tree showing:

●​ Each function call as a node

●​ Base cases as leaf nodes
●​ Track flow of parameters and returned values

📌 Important Recursion Optimizations

●​ Tail Recursion (can be optimized into iteration by compiler — not in Java by default)
●​ Memoization (Top-down DP)
●​ Bottom-up DP (Tabulation)

📌 Recursion Time & Space Complexity

●​ Time Complexity: Number of function calls × time per call
●​ Space Complexity: Call stack depth + extra space

Example:​
For Fibonacci without memoization → O(2^N) time, O(N) space (stack)

📌 Common Mistakes in Recursion

❌ Missing base case​
❌ Incorrect problem size reduction​
❌ Forgetting to return result​
❌ Infinite recursion​
❌ Not visualizing the recursion tree
📌 Recursion — Theory Interview Questions (with answers)
1️⃣ What is Recursion?

Recursion is a technique where a function calls itself directly or indirectly to solve a problem by breaking it
down into smaller subproblems.

2️⃣ What are the essential parts of a recursive function?

●​ Base Case — the stopping condition

 ●​ Recursive Case — the function calling itself with a smaller input

3️⃣ Why is a base case important in recursion?

Without a base case, recursion will continue infinitely, causing a stack overflow error.

4️⃣ What is the difference between direct and indirect recursion?

●​ Direct Recursion — a function calls itself directly​

●​ Indirect Recursion — a function calls another function, which eventually calls the original function

5️⃣ What is a Recursion Tree?

A diagram that visually represents each function call made during recursion, showing how the problem is
divided and the order in which functions return.

6️⃣ What are common real-world problems solved using recursion?

●​ Tree traversals
●​ Graph traversals (DFS)
●​ Tower of Hanoi
●​ Factorial, Fibonacci
●​ Permutations and combinations
●​ Subset generation
●​ Maze/pathfinding problems

7️⃣ What is Tail Recursion?

A recursion where the recursive call is the last statement in the function, with no extra computation after the
call.

8️⃣ What is the difference between Recursion and Iteration?

Feature Recursion Iteration

Uses call stack Yes No

Base case Yes No

needed

More memory Higher (stack) Lower

Simplicity Elegant for complex problems Simpler for repetitive tasks

9️⃣ When should recursion be preferred over iteration?

●​ When a problem can be naturally divided into similar subproblems (trees, backtracking)
●​ When the number of operations isn’t too large to cause stack overflow

🔟 What is Memoization in Recursion?

Storing results of expensive function calls in a data structure (usually a map or array) and reusing the cached
result when the same inputs occur again — used to optimize recursion (top-down Dynamic Programming).

1️⃣1️⃣ What are common mistakes while writing recursion?

●​ Missing or incorrect base case

●​ Not reducing the problem size correctly
 ●​ Forgetting to return a value
●​ Infinite recursion
●​ Mismanaging the recursion stack

1️⃣2️⃣ How is recursion implemented internally?

Each function call is pushed onto the call stack, with its local variables and parameters. The stack unwinds
when base cases are reached.

1️⃣3️⃣ What is Backtracking?

A recursive technique used to explore all possible options and backtrack when a solution fails, commonly used
in:

●​ N-Queens
●​ Sudoku Solver
●​ Subset / Permutation generation

1️⃣4️⃣ What is Divide and Conquer?

A recursive problem-solving strategy where a problem is:

●​ Divided into subproblems

●​ Solved recursively
●​ Combined to get the final result​
Example: Merge Sort, Quick Sort

1️⃣5️⃣ What are the time and space complexities of recursive functions?

●​ Time Complexity = Number of recursive calls × time per call

●​ Space Complexity = Space for the call stack + extra space

Example:​
Fibonacci without memoization → O(2^N) time, O(N) space

📌 Recursion — Rapid Revision (One-Liners & MCQs)

📖 One-Liner Facts:
●​ Recursion is a function calling itself.
●​ Every recursion must have a base case.
●​ Infinite recursion causes a stack overflow error.
●​ Tail recursion has the recursive call as the last operation.
●​ Recursion Tree visualizes recursive calls and their returns.
●​ Memoization optimizes recursion by storing already computed results.
●​ Backtracking is recursion with trial and error.
●​ Divide and Conquer splits a problem, solves recursively, and combines results.
●​ Recursion uses a call stack to keep track of function calls.
●​ A recursive function should reduce the problem size at every call.
●​ Direct recursion calls itself directly; Indirect recursion involves multiple functions.
●​ Time complexity of recursion depends on the number of calls × work per call.
●​ Space complexity is mainly due to the recursion stack.
●​ Tree, graph traversals and problems like N-Queens, Sudoku Solver use recursion.
●​ Recursion works best with problems following a monotonic structure or subproblem pattern.

📖 Quick MCQs
👉
1️⃣ What is required for recursion to terminate?​
Base Case

👉
2️⃣ What causes a stack overflow in recursion?​
Missing/Incorrect base case

👉
3️⃣ Recursion uses which data structure internally?​
Call Stack

👉
4️⃣ Which recursion type has the recursive call at the end of the function?​
Tail Recursion

👉
5️⃣ Which technique stores the result of subproblems to avoid recomputation?​
Memoization

👉
6️⃣ Which of the following is NOT a use case for recursion?​
Bubble Sort (Iterative preferred)

👉
7️⃣ Which strategy splits a problem into parts, solves recursively, and combines?​
Divide and Conquer

👉
8️⃣ What is the biggest risk of using recursion unnecessarily?​
Stack overflow and inefficient performance

👉
9️⃣ Recursion is most naturally used with which data structure?​
Trees

🔟 Which technique tries out options recursively and backtracks if needed?​

👉 Backtracking
✅ Bonus Speed Facts
●​ Merge Sort → Divide and Conquer
●​ Fibonacci (Plain) → O(2^N)
●​ Fibonacci (Memoized) → O(N)
●​ Binary Tree DFS → Recursion
●​ Permutations, Subsets → Backtracking
●​ Tower of Hanoi → Recursion
●​ N-Queens → Backtracking

📌 LeetCode Recursion Problem List (with Company Tags &

Levels)
# Problem Name Level Companies LeetCode
#

1️⃣ Fibonacci Number Easy Amazon, Google 509

2️⃣ Climbing Stairs Easy Amazon, Apple 70

3️⃣ Reverse Linked List Easy Amazon, Microsoft, 206

Google

4️⃣ Maximum Depth of Binary Tree Easy Amazon, Google, 104

Facebook

5️⃣ Symmetric Tree Easy Amazon, Microsoft, 101

Facebook
6️⃣ Subsets Mediu Facebook, Amazon, 78
m Google

7️⃣ Permutations Mediu Amazon, Facebook, 46

m Google

8️⃣ Combination Sum Mediu Amazon, Facebook, 39

m Microsoft

9️⃣ Letter Combinations of a Phone Mediu Amazon, Google, 17

Number m Microsoft

🔟 Generate Parentheses Mediu Google, Facebook, 22

m Amazon

1️⃣1️⃣ Word Search Mediu Amazon, Microsoft, 79

m Google

1️⃣2️⃣ Unique Binary Search Trees Mediu Google, Bloomberg 96

m

1️⃣3️⃣ Subsets II Mediu Amazon, Facebook 90

m

1️⃣4️⃣ N-Queens Hard Amazon, Facebook, 51

Google

1️⃣5️⃣ Palindrome Partitioning Mediu Amazon, Microsoft 131

m

1️⃣6️⃣ Path Sum Easy Amazon, Microsoft, 112

Google

1️⃣7️⃣ Flatten a Multilevel Doubly Linked Mediu Facebook, Microsoft 430

List m

1️⃣8️⃣ Construct Binary Tree from Mediu Amazon, Microsoft, 105

Preorder and Inorder m Google

1️⃣9️⃣ Validate Binary Search Tree Mediu Amazon, Facebook, 98

m Google

2️⃣0️⃣ Merge Two Sorted Lists Easy Amazon, Microsoft, 21

Google

2️⃣1️⃣ Sum Root to Leaf Numbers Mediu Amazon, Microsoft, 129

m Google

2️⃣2️⃣ Recover Binary Search Tree Hard Facebook, Amazon, 99

Google

2️⃣3️⃣ Word Break II Hard Amazon, Google 140

2️⃣4️⃣ Combination Sum II Mediu Amazon, Microsoft, 40

m Google

2️⃣5️⃣ Permutations II Mediu Facebook, Amazon 47

m

2️⃣6️⃣ Count All Valid Pickup and Mediu Amazon, Google 1359
Delivery Options m
2️⃣7️⃣ All Possible Full Binary Trees Mediu Google 894
m

2️⃣8️⃣ Binary Tree Maximum Path Sum Hard Facebook, Amazon, 124
Google

2️⃣9️⃣ Construct Binary Tree from Inorder Mediu Facebook, Amazon 106
and Postorder m

3️⃣0️⃣ Number of Islands Mediu Amazon, Microsoft, 200

m Google

✅ Recursion-Heavy Topics Covered:

●​ Subset/Permutation generation
●​ Divide & Conquer Tree problems
●​ Backtracking & Combinatorics
●​ Recursion with Memoization
●​ Binary Tree Traversals
●​ Dynamic Programming recursion base problems
●​ String-based recursion
●​ DFS-based matrix problems​

📌 Recursion Tricks & Cheatsheet (with Use Cases)

Trick / Pattern Explanation / Code Skeleton Where It’s Used

1. Base Case First Always define your stopping Tree traversal, DFS,
condition first. Factorial, Fibonacci

2. Divide Problem, Call Break input into smaller parts, Tree problems, MergeSort,
Recursively solve them recursively Subset/Permutation
generation

3. Backtracking Add a choice, recurse, then Subsets, Permutations,

(Add-Remove Pattern) undo the choice (backtrack) Combination Sum,
N-Queens

4. Return Value from Recursively collect and return Max Depth of Tree, Binary
Recursion values Tree Path Sum, Min Path
Sum

5. Global / Class-level Use a global variable to track Maximum Path Sum,

Result results across calls Counting Ways

6. Recursion on Left & Recurse on left and right Tree Problems (Inorder,
Right subtree Preorder, Max Path, BST
problems)

7. String Building Append a char, recurse, Letter Combinations,

Recursion remove (backtrack) Parentheses Generation

8. Recursion with Cache already solved Climbing Stairs, Fibonacci,

Memoization (Top-Down subproblems Word Break, Unique Paths
DP)

9. Permutations Swap elements, recurse, swap Permutations,

(Swapping Technique) back Permutations II
10. Subset At each step, include or Subsets, Subset Sum,
(Include/Exclude Pattern) exclude the current element Power Set

11. Recursion on Grid Recursively visit neighbors in Number of Islands, Flood

(DFS Recursion) grid problems Fill, Maze Solving

12. Recursion + Sorting Sort first, avoid duplicates in Combination Sum II,
Trick backtracking Permutations II

13. Tree Construction Use preorder/inorder/postorder Construct Tree from

from Traversals indexes in recursion Preorder &
Inorder/Postorder

14. Recursion with Make multiple recursive calls K-ary tree, generating
Multiple Calls inside a loop combinations or
permutations

15. Binary Search via Recurse on left or right half Rotated Array Search,
Recursion based on condition Peak Element, First/Last
Occurrence

16. Palindrome Check prefix, if palindrome, Palindrome Partitioning,

Partitioning Recursion recurse on suffix Substring Problems

17. Recursion with Pass a counter as argument, Counting Paths, Counting

Counting update during calls Nodes, Balanced Tree
Height

18. Recursion with Return true/false directly from Validate BST, Tree
Boolean Return recursive call Symmetry, Path Existence

19. Recursion by Pass sliced version (arr[1:], Subsequence, Substring,

Shrinking Array/String str[1:]) Word Search

20. Recursion by Index Use a position index to avoid Word Search, Subsets,
array slicing (efficient) Combination Sum

21. Recursion Depth Track recursion level using a N-Queens, Generate

Control depth parameter Parentheses

22. Recursion for Compare values returned by Tree Problems (Max Path
Minimum/Maximum left and right subtrees Sum, Height, Diameter)

23. Recursion for Path Pass a list or string path in Root-to-Leaf Paths, Subset
Tracking recursive calls Generation

24. Recursion with Pass sum/product till the Sum of Digits, Path Sum in
Carry-Forward current recursion depth Binary Tree
Sum/Product

25. Recursion with Object Create deep copies of Clone Graph, Copy Linked
Copies (Deep Copy) structures while recursing List with Random Pointer

26. Recursion for Matrix Move in 4 directions (up, down, Number of Islands,
Traversal left, right) Connected Components in
Matrix

27. Recursion with Choose a fixed set of options Phone Number Letter
Limited Choices at every step Combinations, Generate
Parentheses
28. Recursion with Early Return early if a condition is N-Queens, Backtracking
Pruning met with Constraints

29. Tail Recursion Perform final operation after Factorial, GCD

(optimized) recursive call

30. Recursion for Merge Merge left and right recursively Merge Sort, Merge K Lists
Problems

31. Recursion for Check match, then move Word Search, Pattern
Substring Search ahead recursively Matching

32. Recursion with Shift start/end indices while Substring Problems,

Sliding Window (on call) recursing Maximum Subarray

✅ When & Where to Use These Patterns

Problem Type Suggested Recursion Tricks

Subsets / Permutations / Backtracking, Include/Exclude, Sorting+Skip

Combinations Duplicates

Binary Trees Left/Right Recursion, Return Values, Global Result,

Path Tracking

Grid/Matrix DFS Recursion, Grid Bounds Check, Visited Matrix

Palindrome / Partitioning Palindrome Check + Recursion on Remaining

Substring

DP Recursion (Memoized) Memoization Table / Map

Graph Traversals DFS Recursion, Deep Copy, Visited Set

Binary Search Problems Recursion on Half (left/right), Compare Mid

Counting Problems Recursion with Counting/Carry Sum

Maze / Paths Grid Recursion, Path Tracking, Backtracking

📒 Example — Combination Sum (Backtracking Recursion)

void findCombinations(int[] nums, int target, List<Integer> temp, int index) {
if (target == 0) {
[Link](new ArrayList<>(temp)); // Found valid combination
return;
}
if (target < 0) return;

for (int i = index; i < [Link]; i++) {

[Link](nums[i]); // Choose
findCombinations(nums, target - nums[i], temp, i); // Recurse
[Link]([Link]() - 1); // Backtrack
}
}

✔️ Uses:
●​ Base Case
 ●​ Backtracking (Add-Remove)
●​ Recursion with Index
●​ Recursion with Early Pruning

📑 Recursion Cheatsheet (Java) — with Code, Use-Cases & Tricks

✅ 1. Simple Recursive Call
When to use: Base recursion problems, counting, printing.

void printNum(int n) {
if(n == 0) return;
[Link](n);
printNum(n-1);

✅ 2. Backtracking Template
}

When to use: Combinations, permutations, subsets

void backtrack(List<Integer> list, int start, int[] nums) {

[Link](new ArrayList<>(list));
for(int i=start; i<[Link]; i++) {
[Link](nums[i]);
backtrack(list, i+1, nums);
[Link]([Link]()-1); // backtrack
}

✅ 3. Tail Recursion
}

When to use: When the recursive call is the last operation

void tailRec(int n) {
if(n==0) return;
[Link](n);
tailRec(n-1);

✅ 4. Multiple Recursion Calls

}

When to use: Tree problems, Fibonacci

int fib(int n) {
if(n<=1) return n;
return fib(n-1) + fib(n-2);

✅ 5. Recursion with Return Value

}

When to use: Problems requiring returned results

int sum(int n) {
if(n==0) return 0;
return n + sum(n-1);
}
✅ 6. Recursion + Global/Static Variable
When to use: Carry over state

static int count=0;

void countNodes(TreeNode root) {
if(root==null) return;
count++;
countNodes([Link]);
countNodes([Link]);

✅ 7. Divide and Conquer

}

When to use: Sorting, searching, subproblems

int max(int[] arr, int l, int r) {

if(l == r) return arr[l];
int mid = (l+r)/2;
return [Link](max(arr, l, mid), max(arr, mid+1, r));

✅ 8. Recursion with Memoization (DP)

}

When to use: Overlapping subproblems

int[] dp = new int[100];

int fib(int n) {
if(n<=1) return n;
if(dp[n]!=0) return dp[n];
return dp[n] = fib(n-1) + fib(n-2);

✅ 9. Recursion with Parameter Change

}

When to use: Modifying parameters per call

void reverse(int[] arr, int i, int j) {

if(i>=j) return;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
reverse(arr, i+1, j-1);
}

✅ 10. Recursion on 2D Grid

When to use: Maze, Flood Fill, DFS on Matrix

void dfs(int[][] grid, int i, int j) {

if(i<0 || j<0 || i>=[Link] || j>=grid[0].length || grid[i][j]==0)
return;
grid[i][j]=0;
dfs(grid, i+1, j);
dfs(grid, i-1, j);
dfs(grid, i, j+1);
dfs(grid, i, j-1);
}

✅11. Recursion with Subset Construction

When to use: Subsets, Power sets

void subsets(List<Integer> curr, int[] nums, int idx) {

[Link](new ArrayList<>(curr));
for(int i=idx; i<[Link]; i++) {
[Link](nums[i]);
subsets(curr, nums, i+1);
[Link]([Link]()-1);
}
}

✅ 12. Recursion for String Problems

When to use: Palindromes, permutations

boolean isPalindrome(String s, int i, int j) {

if(i>=j) return true;
if([Link](i)!=[Link](j)) return false;
return isPalindrome(s, i+1, j-1);
}

✅ 13. Recursion for Linked List

When to use: Reverse, Length, Sum

ListNode reverse(ListNode head) {

if(head==null || [Link]==null) return head;
ListNode newHead = reverse([Link]);
[Link] = head;
[Link] = null;
return newHead;

📌 When To Use Which Trick?

}

Technique Problem Types

Simple Recursion Counting, Printing, Basic problems

Backtracking Combinations, Permutations,

Subsets

Tail Recursion Optimizable recursion calls

Multiple Recursions Tree traversal, Fibonacci

Divide & Conquer Sorting, Searching, Max/Min finding

Memoization DP problems like Fib, Climb Stairs

2D Recursion Maze, Grid DFS, Island count

Subset Construction Power sets, combinations

 Linked List Recursion Reverse, Sum, Length of linked list

String Recursion Palindromes, Anagrams, Subsets

📑 Complete Backtracking Notes

📌 What is Backtracking?
Backtracking is a recursive algorithmic technique to solve problems by building a solution incrementally
and removing those solutions that fail to satisfy the constraints at any point of time (backtrack and try
other possibilities).

📌 How It Works
1.​ Choose — Pick an option.
2.​ Explore — Recursively explore this option.
3.​ Unchoose (Backtrack) — Undo the choice and explore other options.

➡️ Think of it like a state-space tree:

●​ Each node represents a state.
●​ If a node leads to a valid solution → take it.
●​ If it violates a constraint → backtrack.

📌 Types of Problems Solved by Backtracking

✅ Permutations​
✅ Combinations​
✅ Subsets / Power Sets​
✅ N-Queens​
✅ Sudoku Solver​
✅ Word Search​
✅ Graph coloring​
✅ Palindrome Partitioning​
✅ Maze problems
📌 General Backtracking Template (Java)
void backtrack(List<Integer> tempList, int[] nums, boolean[] used) {
if([Link]() == [Link]) {
[Link](new ArrayList<>(tempList));
return;
}
for(int i=0; i<[Link]; i++) {
if(used[i]) continue;
used[i] = true;
[Link](nums[i]);
backtrack(tempList, nums, used);
[Link]([Link]()-1); // backtrack
used[i] = false;
}
}

📌 Backtracking vs Recursion
 Recursion Backtracking

Explores all possible Prunes/abandons invalid states

states

Simple brute force Optimized brute force with pruning

No reversal of decisions Undo (backtrack) to try other possibilities

📌 Important Tricks & Techniques

Trick / Pattern Used In Problems

For-Loop Recursion Combinations, Subsets

Boolean Array to Track Choices Permutations, N-Queens

Unchoose (Backtrack) after All backtracking problems

recursion

Base Case = Valid Solution Subsets, Combinations

Base Case = Invalid State N-Queens, Sudoku, Graph Coloring

Backtracking on 2D Grids Maze problems, Word Search, Flood Fill

📌 Common Backtracking Problems & Approach

Problem Pattern Idea

Permutations Pick elements one-by-one Use a used[] array

Combinations For-loop based recursion Use start index to avoid

duplicates

Subsets Include / Exclude pattern Use result list to store

N-Queens Place a queen safely, Use column, diagonal tracking

backtrack

Sudoku Solver Try filling digits 1–9 Backtrack if invalid

Word Search DFS with backtracking Mark cell as visited

Palindrome Check palindrome substring Recurse for the remaining

Partitioning

📌 Sample Codes
✔️ Permutations
void permute(int[] nums, List<Integer> temp, boolean[] used) {
if([Link]() == [Link]) {
[Link](new ArrayList<>(temp));
return;
}
for(int i=0; i<[Link]; i++) {
if(used[i]) continue;
used[i] = true;
[Link](nums[i]);
 permute(nums, temp, used);
[Link]([Link]()-1);
used[i] = false;
}
}

✔️ Combinations
void combine(int n, int k, int start, List<Integer> temp) {
if([Link]() == k) {
[Link](new ArrayList<>(temp));
return;
}
for(int i=start; i<=n; i++) {
[Link](i);
combine(n, k, i+1, temp);
[Link]([Link]()-1);
}
}

✔️ Subsets
void subsets(int[] nums, int index, List<Integer> temp) {
[Link](new ArrayList<>(temp));
for(int i=index; i<[Link]; i++) {
[Link](nums[i]);
subsets(nums, i+1, temp);
[Link]([Link]()-1);
}
}

✔️ N-Queens
void solveNQueens(int n, int row, char[][] board) {
if(row == n) {
// add board to result
return;
}
for(int col=0; col<n; col++) {
if(isSafe(board, row, col)) {
board[row][col] = 'Q';
solveNQueens(n, row+1, board);
board[row][col] = '.'; // backtrack
}
}
}

📌 Time and Space Complexity

Problem Time Complexity Space
Complexity

Permutations O(N!) O(N)

 Combinations (n choose O(2^N) O(N)
k)

Subsets O(2^N) O(N)

N-Queens O(N!) O(N^2)

Sudoku Solver O(9^m) O(1)

📌 Common Mistakes
❌ Forgetting to backtrack (undo choices)​
❌ Skipping base cases​
❌ Not handling duplicate values (use sorting + skip conditions)​
❌ Not properly tracking used elements
📌 Backtracking Summary
✔ Recursive​
✔ State-based decision tree​
✔ Try → Explore → Undo (backtrack)​
✔ Prunes invalid/unpromising branches​
✔ Efficient for combinatorial, constraint-satisfaction problems

⚡ Backtracking Rapid Revision — One-Liners

1️⃣ Backtracking is recursion with state reversal.​
2️⃣ "Choose, Explore, Unchoose" is the core pattern.​
3️⃣ Use a boolean used[] array to track picked elements in permutations.​
4️⃣ Combinations problems use for-loop recursion with a start index.​
5️⃣ Subsets are combinations where you explore with or without each element.​
6️⃣ Always undo your choice after recursive calls — that’s backtracking.​
7️⃣ In N-Queens, track columns and diagonals to validate safe positions.​
8️⃣ Backtracking works best on problems with multiple possible states.​

🔟
9️⃣ Sudoku uses a nested backtracking loop over rows and columns.​
Word Search uses 2D DFS with backtracking — mark cells as visited.​
1️⃣1️⃣ Palindrome Partitioning involves checking substrings for palindromes before recursing.​
1️⃣2️⃣ Sort input and skip duplicates for unique permutations or combinations.​
1️⃣3️⃣ Backtracking avoids invalid solutions early — pruning saves time.​
1️⃣4️⃣ Backtracking problems often ask for ‘all possible’, ‘valid combinations’, or ‘ways to arrange’.​
1️⃣5️⃣ Base case is reached when a full valid state or invalid condition occurs.​
1️⃣6️⃣ A result list is maintained to collect valid solutions.​
1️⃣7️⃣ Backtracking problems usually have exponential time complexity — O(2^N) or O(N!).​
1️⃣8️⃣ Use List<Integer> or List<String> to maintain current state in recursion.​
1️⃣9️⃣ Use global or passed-by-reference result lists for final answers.​
2️⃣0️⃣ Try every option, move forward recursively, and backtrack if it doesn't work.​
2️⃣1️⃣ If you forget to unchoose (backtrack), your code will give wrong or incomplete results.​
2️⃣2️⃣ In permutations with duplicates, sort and skip repeated numbers using if (i > 0 && nums[i]
== nums[i-1] && !used[i-1]) continue.​
2️⃣3️⃣ For combinations with fixed size, stop recursion when [Link]() == k.​
2️⃣4️⃣ When dealing with 2D problems (Maze, Word Search) — always mark cell as visited before
recursion and unmark after.​
2️⃣5️⃣ Recursion + for-loop = combinations / subsets; recursion + boolean array = permutations.

1. HashMap
A HashMap in Java stores data in key-value pairs. It allows constant-time complexity (O(1)) for most
operations like insertion, deletion, and access. The data is not ordered in a HashMap.

Key Properties:

●​ Unordered: Elements do not maintain any order.

●​ Allows null: Both keys and values can be null.
●​ Not synchronized: It's not thread-safe.
●​ Uses hashing: HashMap uses a hash table for storage.
●​ Key-value pairs: Each key is unique, but the values can be duplicated.

Common Methods:
put(K key, V value) // Adds key-value pair
get(Object key) // Returns value for given key
containsKey(Object key) // Checks if the key exists
remove(Object key) // Removes the key-value pair
keySet() // Returns a set of keys
values() // Returns a collection of values
size() // Returns the number of entries
clear() // Clears all entries

Time Complexity:

●​ Insert: O(1)
●​ Delete: O(1)
●​ Search: O(1)
●​ Resize: O(n) in worst case during resizing (rehashing).

2. HashSet
A HashSet is a collection that does not allow duplicate elements. It does not maintain order and is based on
hashing.

Key Properties:

●​ Unordered: The elements in a HashSet are not stored in any specific order.
●​ No duplicates: It does not allow duplicate values.
●​ Hashing: HashSet uses a hash table for storage, similar to HashMap but without key-value pairs.
●​ Allows null: One null element is allowed.
●​ Not synchronized: It is not thread-safe.

Common Methods:
add(E e) // Adds the element if not present
remove(Object o) // Removes the specified element
contains(Object o) // Checks if the element is present
size() // Returns the number of elements
clear() // Removes all elements
isEmpty() // Checks if the set is empty

Time Complexity:

●​ Insert: O(1)
●​ Delete: O(1)
 ●​ Search: O(1)

3. TreeSet
A TreeSet is a Sorted Set based on a Red-Black Tree structure. The elements in a TreeSet are ordered
(natural order or by a comparator).

Key Properties:

●​ Sorted order: The elements are stored in a sorted order.

●​ No duplicates: It does not allow duplicate elements.
●​ Uses Red-Black Tree: TreeSet uses a Red-Black Tree for storage.
●​ Performance: Operations like insertion, deletion, and lookup take O(log n) time.
●​ Not synchronized: It is not thread-safe.

Common Methods:
add(E e) // Adds the element if not present
remove(Object o) // Removes the specified element
contains(Object o) // Checks if the element is present
first() // Returns the first element
last() // Returns the last element
size() // Returns the number of elements
clear() // Removes all elements

Time Complexity:

●​ Insert: O(log n)
●​ Delete: O(log n)
●​ Search: O(log n)

4. LinkedHashSet
A LinkedHashSet is a combination of a HashSet and a LinkedList. It maintains insertion order while
providing constant-time performance for basic operations.

Key Properties:

●​ Ordered: Maintains the insertion order of elements.

●​ No duplicates: Does not allow duplicate elements.
●​ Faster: While providing ordering, it offers performance close to HashSet.
●​ Uses HashMap: It internally uses a HashMap to store the elements and a Linked List for maintaining
the insertion order.
●​ Not synchronized: It is not thread-safe.

Common Methods:
add(E e) // Adds the element if not present
remove(Object o) // Removes the specified element
contains(Object o) // Checks if the element is present
size() // Returns the number of elements
clear() // Removes all elements
isEmpty() // Checks if the set is empty
Time Complexity:

●​ Insert: O(1)
●​ Delete: O(1)
●​ Search: O(1)

Comparisons:
Feature HashMap HashSet TreeSet LinkedHashSet

Order No No Yes (Sorted) Yes (Insertion)

Duplicates No No No No

Null Elements Yes Yes No Yes

Performance O(1) O(1) O(log n) O(1) average

average average

Underlying Structure Hash Table Hash Table Red-Black Tree Hash Table + Linked List

Synchronization No No No No

HashMap:

1.​ What is a HashMap, and how does it work?

○​ A HashMap is a collection that stores data in key-value pairs. Internally, it uses a hash table to
store the keys and their corresponding values. The keys are hashed using a hash function, and
this helps in achieving O(1) average time complexity for insertion, deletion, and lookup
operations.
2.​ How does a HashMap handle collisions?
○​ HashMap handles collisions using chaining or open addressing. In chaining, each bucket of
the hash table stores a linked list of entries that hash to the same bucket. In open addressing,
when a collision occurs, a probing sequence is followed to find an empty bucket.
3.​ What is the difference between HashMap and Hashtable?
○​ Hashtable is synchronized and thread-safe, while HashMap is not synchronized. This makes
HashMap faster in non-concurrent applications. Additionally, Hashtable does not allow null
keys or values, while HashMap allows one null key and multiple null values.
4.​ What is the initial capacity and load factor of a HashMap?
○​ The initial capacity of a HashMap is the number of buckets in the hash table, and the load
factor is the threshold that determines when to resize the hash table. By default, the initial
capacity is 16 and the load factor is 0.75.
5.​ What is the time complexity of basic operations in HashMap?
○​ Insert, Delete, Lookup: O(1) on average.
○​ Worst-case: O(n) when many collisions occur.​

HashSet:

1.​ What is a HashSet, and how does it work?

○​ A HashSet is a collection that stores unique elements, and it is based on HashMap internally. It
does not maintain any order, and operations like add, remove, and contains have an average
time complexity of O(1).
2.​ What is the difference between HashSet and TreeSet?
○​ HashSet does not maintain any order, while TreeSet maintains elements in a sorted order
based on their natural ordering or a comparator.
○​ TreeSet is implemented using a Red-Black Tree, and its operations have a time complexity of
O(log n), whereas HashSet operations have a time complexity of O(1) on average.
 3.​ Can you store null elements in a HashSet?
○​ Yes, a HashSet allows only one null element.
4.​ What are the time complexities for common operations in a HashSet?
○​ Add, Remove, Contains: O(1) on average.
○​ Worst-case: O(n) when there are hash collisions.

TreeSet:

1.​ What is a TreeSet, and how does it work?

○​ A TreeSet is a Sorted Set that stores unique elements in a sorted order. It is implemented
using a Red-Black Tree, which is a self-balancing binary search tree.
2.​ How does TreeSet maintain the order of elements?
○​ TreeSet uses the natural ordering of elements (for Comparable objects) or a Comparator to
maintain order.
3.​ What is the time complexity for TreeSet operations?
○​ Add, Remove, Contains: O(log n) due to the Red-Black Tree structure.
4.​ Can a TreeSet store null elements?
○​ No, a TreeSet does not allow null elements, as they cannot be compared.
5.​ How is a TreeSet different from a HashSet?
○​ HashSet is unordered, while TreeSet maintains the elements in sorted order. TreeSet has a
higher time complexity (O(log n)) for basic operations compared to HashSet (O(1)).

LinkedHashSet:

1.​ What is a LinkedHashSet, and how does it work?

○​ A LinkedHashSet is a combination of HashSet and LinkedHashMap. It stores unique
elements like a HashSet, but it also maintains the insertion order using a doubly linked list.
2.​ How is LinkedHashSet different from HashSet?
○​ While both HashSet and LinkedHashSet do not allow duplicates, LinkedHashSet maintains
the insertion order of elements, whereas HashSet does not maintain any order.
3.​ Can a LinkedHashSet store null elements?
○​ Yes, a LinkedHashSet can store one null element.
4.​ What is the time complexity for operations in a LinkedHashSet?
○​ Add, Remove, Contains: O(1) on average (similar to HashSet).
○​ However, the additional insertion order maintenance causes slight overhead, but still
maintains O(1) time complexity for most operations.
5.​ What are the uses of LinkedHashSet?
○​ LinkedHashSet is useful when you need to maintain the insertion order of elements while
eliminating duplicates, such as when preserving the order of processing elements in an
application.

General Questions:
1.​ When would you choose a HashMap over a HashSet, TreeSet, or LinkedHashSet?
○​ Use a HashMap when you need to store key-value pairs and need fast access to values
based on keys. Use a HashSet when you just need a collection of unique elements without any
need for ordering. Use a TreeSet when you need to store elements in a sorted order. Choose
LinkedHashSet if you need to maintain insertion order along with uniqueness.
2.​ What are the advantages and disadvantages of using HashSet and HashMap?
○​ Advantages: Fast operations (average O(1) time complexity), no duplicates.
○​ Disadvantages: Unordered data (for HashSet) and no guarantee of insertion order.
3.​ Can HashSet store duplicate elements?
○​ No, HashSet does not allow duplicates. Any attempt to add a duplicate element is ignored.
4.​ What is the underlying data structure used in HashSet and HashMap?
○​ Both HashSet and HashMap use a hash table internally. A HashSet uses a HashMap
internally for storage, while HashMap stores data in key-value pairs.
HashMap:
# Problem Name LeetCode Difficulty Company Topics
No Tags

1 Two Sum 1 Easy Amazon, HashMap, Array,

Facebook Two Pointers

2 Isomorphic Strings 205 Easy Google, HashMap, String

Amazon

3 Count Distinct Numbers on 532 Medium Uber HashMap

Board

4 Longest Substring Without 3 Medium Facebook, HashMap, Sliding

Repeating Characters Amazon Window

5 Subarray Sum Equals K 560 Medium Microsoft, HashMap, Array,

Google Prefix Sum

6 Group Anagrams 49 Medium Google, HashMap, String

Amazon

7 Top K Frequent Elements 347 Medium Google, HashMap, Heap,

Facebook Bucket Sort

8 Valid Anagram 242 Easy Amazon, HashMap, String

Microsoft

9 Map Sum Pairs 677 Medium Uber HashMap, Prefix

Sum

10 Least Number of Unique 910 Medium Amazon, HashMap, Heap,

Integers After K Removals Google Greedy

HashSet:
# Problem Name LeetCode Difficulty Company Topics
No Tags

1 Happy Number 202 Easy Amazon, HashSet, Math,

Facebook Slow-Fast Pointers

2 Intersection of Two 349 Easy Facebook, HashSet, Array

Arrays Google

3 Contains Duplicate 217 Easy Microsoft, HashSet, Array

Amazon

4 Two Sum II - Input Array 167 Easy LinkedIn, HashSet, Two

Is Sorted Facebook Pointers, Sorting

5 Valid Sudoku 36 Medium Google, HashSet, Matrix

Microsoft

6 Disjoint Set of Intervals 1288 Medium Facebook, HashSet, Interval,

Microsoft Sorting
7 Number of Unique Emails 929 Easy Google, HashSet, String
Microsoft

8 Find All Duplicates in an 442 Medium Google, HashSet, Array

Array Facebook

9 Longest Consecutive 128 Hard Google, HashSet, Array,

Sequence Microsoft Union-Find

10 Remove Duplicates from 26 Easy Amazon, HashSet, Array, Two

Sorted Array Facebook Pointers

TreeSet:
# Problem Name LeetCode Difficulty Company Topics
No Tags

1 Kth Largest Element in a 703 Easy Microsoft, TreeSet, Heap

Stream Facebook

2 Insert into a Binary Search 701 Medium Google, TreeSet, BST

Tree Facebook

3 Find Median from Data Stream 295 Hard Amazon, TreeSet, Heap
Google

4 Merge Intervals 56 Medium Facebook, TreeSet, Interval

Google

5 Sliding Window Maximum 239 Hard Facebook, TreeSet, Sliding

Microsoft Window

6 Binary Search Tree Iterator 173 Medium Google, TreeSet, BST,

LinkedIn Iterator

7 Inorder Successor in BST 285 Medium Amazon, TreeSet, BST

Google

8 Find the Smallest Range 632 Hard Google, TreeSet, Interval

Covering Elements from K Facebook
Lists

9 Balanced Binary Tree 110 Easy Microsoft, TreeSet, BST

Google

10 Remove Invalid Parentheses 301 Hard Facebook, TreeSet,

Google Backtracking

LinkedHashSet:
# Problem Name LeetCode Difficulty Company Topics
No Tags

1 Remove Duplicates from 26 Easy Amazon, LinkedHashSet, Array,

Sorted Array Facebook Two Pointers

2 LRU Cache 146 Medium Facebook, LinkedHashSet, Cache,

Uber Design
3 Find All Numbers 448 Easy Microsoft, LinkedHashSet, Array
Disappeared in an Array Amazon

4 Unique Email Addresses 929 Easy Google, LinkedHashSet, String

Microsoft

5 Permutation in String 567 Medium Google, LinkedHashSet, String,

Facebook Sorting

6 Insert Delete 380 Medium Amazon, LinkedHashSet,

GetRandom O(1) Google Random Access

7 Linked List Cycle II 142 Medium Google, LinkedHashSet, Linked

Facebook List

8 Remove Invalid 301 Hard Facebook, LinkedHashSet,

Parentheses Google Backtracking

9 Count of Smaller 315 Hard Google, LinkedHashSet, Binary

Numbers After Self Amazon Indexed Tree

10 Top K Frequent Words 692 Medium Google, LinkedHashSet,

Amazon HashMap

HashMap Cheatsheet:

Basic Operations:

●​ Insertion: [Link](key, value)

●​ Deletion: [Link](key)
●​ Get Value: [Link](key)
●​ Check Key Existence: [Link](key)
●​ Check Value Existence: [Link](value)
●​ Size: [Link]()
●​ Iterating:
○​ Using entrySet:​
for ([Link]<K, V> entry : [Link]()) { ... }
○​ Using keySet:​
for (K key : [Link]()) { ... }
○​ Using values:​
for (V value : [Link]()) { ... }

Use Cases:

●​ Counting Frequency of Elements:​

Map<Character, Integer> freqMap = new HashMap<>();

Two Sum Problem:​

Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < [Link]; i++) {
int complement = target - nums[i];
if ([Link](complement)) {
return new int[] {[Link](complement), i};
}
[Link](nums[i], i);
}
 ●​ Group Anagrams:​
Use the sorted characters of each string as the key, and the list of anagrams as the value in the map.​

HashSet Cheatsheet:

Basic Operations:

●​ Insertion: [Link](element)
●​ Deletion: [Link](element)
●​ Contains Check: [Link](element)
●​ Size: [Link]()
●​ Iterating:​
for (T element : set) { ... }

Use Cases:
Removing Duplicates from an Array:​
Set<Integer> set = new HashSet<>();
for (int num : nums) {
[Link](num);
}
Finding Intersection of Two Arrays:​
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for (int num : nums1) [Link](num);
for (int num : nums2) [Link](num);
[Link](set2);

Checking if a Number is Happy (Set to track visited states):​

Set<Integer> set = new HashSet<>();
while (num != 1 && ) {
[Link](num);
num = getNext(num);
}

TreeSet Cheatsheet:

Basic Operations:

●​ Insertion: [Link](element)
●​ Deletion: [Link](element)
●​ Contains Check: [Link](element)
●​ Size: [Link]()
●​ Iterating:​
for (T element : treeSet) { ... }

Use Cases:
Kth Largest Element in a Stream (Use TreeSet to maintain sorted order):​
NavigableSet<Integer> set = new TreeSet<>();
for (int num : nums) {
[Link](num);
if ([Link]() > k) [Link](); // remove smallest element
}
return [Link](); // kth largest element
Range Queries:​
To find all elements within a range [low, high], use subSet(low, true, high, true):​
NavigableSet<Integer> subset = [Link](low, true, high, true);
for (int num : subset) { ... }

LinkedHashSet Cheatsheet:

Basic Operations:

●​ Insertion: [Link](element)
●​ Deletion: [Link](element)
●​ Contains Check: [Link](element)
●​ Size: [Link]()
●​ Iterating:​
for (T element : linkedHashSet) { ... }

Use Cases:

●​ Maintaining Insertion Order (LinkedHashSet preserves order):

○​ Useful when order of elements matters, e.g., Removing Duplicates While Keeping Original
Order:​
​
Set<Integer> set = new LinkedHashSet<>();

for (int num : nums) {

[Link](num);
}
LRU Cache (LinkedHashSet can be used for eviction mechanism in cache):​
Set<Integer> set = new LinkedHashSet<>(capacity, 0.75f, true);

○​ Eviction Policy: Remove least recently used elements when the cache exceeds the capacity.​

General Tips for Using These Data Structures:

●​ HashMap:
○​ Time Complexity: Average O(1) for insertions, deletions, and lookups.
○​ When to use: Ideal for searching, inserting, and deleting data based on a key.
○​ Limitations: Hash collisions can affect performance.
●​ HashSet:
○​ Time Complexity: Average O(1) for insertions, deletions, and lookups.
○​ When to use: Ideal for checking membership or removing duplicates.
○​ Limitations: Doesn't allow duplicates and doesn't preserve any order.
●​ TreeSet:
○​ Time Complexity: O(log n) for insertions, deletions, and lookups due to tree structure.
○​ When to use: Useful when you need sorted data, or when you need to perform range queries.
○​ Limitations: Slower compared to HashSet for unordered sets due to sorting.
●​ LinkedHashSet:
○​ Time Complexity: O(1) for insertions, deletions, and lookups.
○​ When to use: Ideal when maintaining the order of insertion is important.
○​ Limitations: Slightly slower than HashSet due to maintaining insertion order.​
Applications in Problems:

1.​ HashMap:
○​ Frequency Counting (e.g., Two Sum, Group Anagrams, Subarray Sum)
○​ Caching (e.g., LRU Cache)
○​ Searching for Complementary Values (e.g., Two Sum)
2.​ HashSet:
○​ Removing Duplicates (e.g., Intersection of Two Arrays)
○​ Checking Membership (e.g., Happy Number)
○​ Set Operations (e.g., Union, Intersection, Difference)
3.​ TreeSet:
○​ Kth Largest Element (e.g., Top K Frequent Elements)
○​ Sorted Data Storage (e.g., Range Queries)
○​ Order-Sensitive Operations (e.g., Balanced BST, Range Search)
4.​ LinkedHashSet:
○​ Maintaining Insertion Order (e.g., Removing Duplicates with Order)
○​ LRU Cache (e.g., Recently Used Cache Eviction)

Advanced Operations:

●​ HashMap

Merge Maps:​
[Link](map2);

●​ HashSet:

Union (with another set):​

[Link](set2);

●​ TreeSet:

Finding Ceiling and Floor Values:​

[Link](x); // Returns smallest element >= x
[Link](x); // Returns largest element <= x

○​