TRT
Sign in

Advanced · Module 21 · Lesson 3 of 4

Combinatorial Search Patterns: Subsets, Permutations, Pruning, and Meet-in-the-Middle

Master the unified choose-explore-unchoose backtracking templates for Subsets, Combinations, and Permutations with duplicate pruning, and halve exponential exponents from O(2^40) to O(2^20) with Meet-in-the-Middle.

Pro — members onlyAbout 18 minutes

By the end you can

  • Distinguish Subsets/Combinations (pass start index i + 1) from Permutations (swap or used[] boolean mask) and With-Replacement (pass i)
  • Prevent duplicate branches on arrays with repeated values by sorting first and skipping i > start && nums[i] == nums[i - 1]
  • Cut O(2^N) subset-sum searches for N <= 40 down to O(2^(N/2) log(2^(N/2))) using Meet-in-the-Middle

Builds on Backtracking basics, Binary search without off-by-one bugs.

01 · A question first

For N = 40 items, checking all 2^40 subsets takes 1.1 trillion steps (~18 minutes)—an instant Time Limit Exceeded. Splitting the 40 items into two halves of 20 items each needs only 2 * 2^20 = 2 million steps (~15 milliseconds)! How does Meet-in-the-Middle stitch the two halves together?

Make a guess before you read on.

02 · The idea

Members only

Unlock the full lesson

This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.

What's inside

  • Intuitive Explanation & Real-World Analogy
  • Core Concepts & Visual Walkthrough
  • Pseudocode
  • Multi-Language Implementations (C++, Java, Python)
  • Time & Auxiliary Space Complexity Derivation
  • Edge Cases & Common Beginner Mistakes
  • Alternative Approaches (Brute Force vs. Optimal)
  • Pattern Recognition Guide & Three-Stage Practice Plan
See plansAlready a member? Sign in

03 · Practice

Practice · medium · LeetCodeSubsetsReturn every subset of a set of distinct integers, using backtracking with a start index.Practice · medium · LeetCodePermutationsReturn every ordering of an array of distinct integers, tracking which elements are already used.Practice · medium · LeetCodeCombination sumFind every combination of candidates, each usable any number of times, that adds up to a target, pruning once the sum is too large.Practice · medium · LeetCodeWord searchDecide whether a word can be traced through adjacent cells of a letter grid, marking cells as used and unmarking them on the way back.

Asked in interviews

Something wrong with this lesson? Report a problem