29. 0/1 Knapsack Pattern & Partition Equal Subset Sum • Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep • Rishabh Ki Kaksha

Data Structures & Algorithms: Blind 75 & Big Tech Interview Prep › 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum

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

# 29. 0/1 Knapsack Pattern & Partition Equal Subset Sum

> DSA Blind 75 Notes by Rishabh - Topic 29

---

### 1. The 0/1 Knapsack Blueprint 🎒

Har item ke liye 2 choices:
1. **0 (Exclude):** Value = $dp[i-1][w]$
2. **1 (Include):** Value = $\text{val}[i] + dp[i-1][w - \text{wt}[i]]$
$$dp[i][w] = \max(dp[i-1][w], \text{val}[i] + dp[i-1][w - \text{wt}[i]])$$

---

### 2. LeetCode #416: Partition Equal Subset Sum ($O(N \cdot \text{Target})$)

*Problem:* Check karo kya array ko do equal sum subsets me partition kiya ja sakta hai.
$$\text{Target} = \frac{\sum \text{nums}}{2} \text{ (If sum is odd } \rightarrow \text{ impossible!)}$$

```python
def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False
        
    target = total // 2
    dp = set([0]) # Stores all reachable sums
    
    for num in nums:
        next_dp = set()
        for t in dp:
            if t + num == target:
                return True
            next_dp.add(t + num)
            next_dp.add(t)
        dp = next_dp
        
    return target in dp
```

---

### 3. 1D Array Space Optimization for 0/1 Knapsack (Reverse Loop Trap 🪤)

```python
# When optimizing 0/1 Knapsack to 1D array, loop in REVERSE:
for num in nums:
    for j in range(target, num - 1, -1): # ⚠️ REVERSE prevents using same item twice!
        dp[j] = dp[j] or dp[j - num]
```

---

### 4. Master Comparison Matrix

| Knapsack Type | Item Reusability | 1D Inner Loop Direction | Example |
| :--- | :--- | :--- | :--- |
| **0/1 Knapsack** | ❌ Exactly Once | **Reverse (`target` to `num`)** | Partition Equal Subset Sum |
| **Unbounded Knapsack**| ✅ Infinite Times | **Forward (`num` to `target`)** | Coin Change, Rod Cutting |

---

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

1. **0/1 Knapsack me reverse loop kyu zaroori hota hai?** -> Taaki current item usi iteration me calculate huye naye values ko reuse na kar sake (Single-use guarantee).
2. **Target Sum (LeetCode #494) 0/1 Knapsack me kaise convert hoti hai?** -> Subsets sum equation: $S_1 - S_2 = \text{target} \implies S_1 = \frac{\text{total} + \text{target}}{2}$.
3. **Knapsack pseudo-polynomial time kyu kehlati hai?** -> Kyunki time complexity $O(N \cdot W)$ input capacity $W$ ki numeric value par depend karti hai, input bits length par nahi.

---
**Next Topic:** 30. Bit Manipulation Tricks: Number of 1 Bits (Hamming Weight), Counting Bits & Missing Number

Loading lesson content...

JavaScript

Live Execution Terminal

Click "Execute Live" to run code.
                