25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search

50 mins

← Prev Next →

Course Syllabus

Module 1: Big-O Asymptotics, Arrays & Sliding Window

01. Time & Space Complexity Masterclass: Big-O, Big-Theta, Big-Omega & Amortized Analysis 02. Arrays & Hashing: Two Sum, Contains Duplicate & Valid Anagram (Hash Table Lookups) 03. Prefix Sum & Kadane's Algorithm (Maximum Subarray Problem in O(N)) 04. Sliding Window Pattern: Fixed vs Dynamic Windows (Best Time to Buy/Sell Stock)

Module 2: Two Pointers & Binary Search Systems

05. Two Pointers Pattern: Valid Palindrome, 3Sum & Container With Most Water 06. Binary Search Foundations: Search in Rotated Sorted Array & Find Minimum 07. Binary Search on Answer Space: Koko Eating Bananas & Capacity to Ship Packages

Module 3: Linked Lists & Fast-Slow Pointer Patterns

08. Singly vs Doubly Linked Lists & In-Place Pointer Manipulation (Reverse Linked List) 09. Fast & Slow Pointer (Floyd's Cycle Detection): Linked List Cycle & Middle Node 10. Merging & Reordering: Merge Two Sorted Lists, Reorder List & Remove Nth Node

Module 4: Stacks, Queues & Monotonic Stack Architecture

11. Stack Fundamentals: Valid Parentheses & Min Stack in O(1) Time 12. Monotonic Stack Pattern: Daily Temperatures & Next Greater Element 13. Hard Stack Coding: Largest Rectangle in Histogram & Trapping Rain Water

Module 5: Trees, Binary Search Trees & DFS/BFS Traversals

14. Binary Tree Architecture: Max Depth, Same Tree & Invert Binary Tree 15. BFS Level-Order Traversal & Binary Tree Right Side View 16. Binary Search Tree (BST) Properties: Validate BST & Lowest Common Ancestor (LCA) 17. Tree Path Sums & Serialize / Deserialize Binary Tree (Hard)

Module 6: Heaps, Priority Queues & Top-K Problems

18. Min Heap & Max Heap Internals: Array Representation & Heapify in O(N) 19. Top-K Elements Pattern: Kth Largest Element in an Array & Top K Frequent Elements 20. Two-Heap Pattern: Find Median from Data Stream (Hard)

Module 7: Graphs, Topological Sort & Shortest Paths (Dijkstra)

21. Graph Representations (Adjacency Matrix vs List) & DFS/BFS Traversal 22. Matrix Graph Traversal: Number of Islands, Max Area of Island & Clone Graph 23. Topological Sort (Kahn's Algorithm): Course Schedule I & II (Cycle Detection) 24. Disjoint Set Union (DSU / Union-Find): Redundant Connection & Number of Connected Components

Module 8: Dynamic Programming, Backtracking & Bit Manipulation

25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change 27. Longest Increasing Subsequence (LIS): O(N^2) DP vs O(N log N) Patience Sort 28. 2D Dynamic Programming: Unique Paths, Longest Common Subsequence (LCS) & Edit Distance 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Interactive Lesson Studio

# 25. Backtracking Pattern: Subsets, Permutations, Combination Sum & Word Search

> DSA Blind 75 Notes by Rishabh - Topic 25

---

### 1. The Backtracking Blueprint (Choose ➔ Explore ➔ Un-Choose 🔄)

Backtracking brute-force search space me state tree traverse karta hai:

```
def backtrack(candidate, state):
    if is_solution(candidate):
        output(candidate)
        return
        
    for choice in choices:
        make_choice(choice)       # 1. CHOOSE
        backtrack(candidate, state)# 2. EXPLORE
        undo_choice(choice)       # 3. UN-CHOOSE (Backtrack!)
```

---

### 2. LeetCode #78: Subsets (Power Set $O(2^N)$)

```python
def subsets(nums: list[int]) -> list[list[int]]:
    res = []
    subset = []
    
    def dfs(i):
        if i >= len(nums):
            res.append(subset.copy())
            return
            
        # 1. Decision to INCLUDE nums[i]:
        subset.append(nums[i])
        dfs(i + 1)
        
        # 2. Decision to EXCLUDE nums[i] (Backtrack!):
        subset.pop()
        dfs(i + 1)
        
    dfs(0)
    return res
```

---

### 3. LeetCode #39: Combination Sum

Elements ko multiple times reuse karne ki permission hai:

```python
def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    res = []
    
    def dfs(i, current, total):
        if total == target:
            res.append(current.copy())
            return
        if i >= len(candidates) or total > target:
            return
            
        # Include candidates[i] (stay at index i):
        current.append(candidates[i])
        dfs(i, current, total + candidates[i])
        
        # Exclude & move forward:
        current.pop()
        dfs(i + 1, current, total)
        
    dfs(0, [], 0)
    return res
```

---

### 4. Master Comparison Matrix

| Problem | Total States | Can Reuse Elements? | Loop vs Decision Tree |
| :--- | :--- | :--- | :--- |
| **Subsets** | $O(2^N)$ | ❌ No | Binary Decision Tree (Include / Exclude) |
| **Permutations (LC #46)**| $O(N!)$ | ❌ No | Loop over unvisited with `visited` set |
| **Combination Sum** | Exponential | ✅ Yes (Stay at index $i$) | Decision Tree with `total > target` pruning |

---

### 5. Interview Ke 3 Sawal Is Topic Se

1. **Subsets II (with duplicate numbers in array) me duplicate sets kaise avoid karte hain?** -> Array sort karo aur backtrack karte waqt loop me `if i > start and nums[i] == nums[i-1]: continue` check lagao.
2. **N-Queens (LeetCode #51 Hard) me diagonal attacks $O(1)$ me kaise check hote hain?** -> Hash sets maintain karke: positive diagonal $(r + c)$ aur negative diagonal $(r - c)$.
3. **Backtracking aur DFS me kya difference hai?** -> DFS poore graph/tree ko traverse karta hai; Backtracking decision tree traverse karte waqt invalid paths ko early prune (discard) karke state un-choose karta hai.

---
**Next Topic:** 26. 1D Dynamic Programming: Climbing Stairs, House Robber & Coin Change

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                