Subsets (Include/Exclude) — Backtracking Patterns
The Subsets (Include/Exclude) pattern applies when you need the Subsets (Include/Exclude) technique within the Backtracking Patterns pattern. Its time complexity is O(2ⁿ) and space complexity O(n) recursion depth. It is used in 4 problems on Thita, including Combinations, Letter Combinations of a Phone Number and Subsets. Common variations are N-Queens / Constraint Satisfaction and Parentheses Generation.
Generate all subsets using include/exclude decision pattern. Handle duplicates in subsets.
Subsets (Include/Exclude) is one of the 7 subpatterns of the Backtracking Patterns pattern, which covers subsets, permutations, combinations, N-Queens, and word search. The whole pattern is about 3 hours of study. This subpattern is a core technique: expect it to come up directly in interviews.
What Subsets (Include/Exclude) covers
Master backtracking algorithms including subsets, permutations, combinations, N-Queens, and word search. Exhaustive search with pruning for constraint satisfaction. Problems in this subpattern are usually searched for as subsets, power set, include exclude, generate subsets, leetcode 78, leetcode 90.
How to practise Subsets (Include/Exclude) on Thita.ai
Read the theory for Subsets (Include/Exclude), then work the problems attached to it in the browser editor. Your solution runs against the problem's test cases, and the AI coach offers a hint about the technique you are missing rather than a finished solution. Progress is tracked per subpattern, so the Backtracking Patterns tracker shows this one as covered once you have solved its problems.
Other subpatterns in Backtracking Patterns
- Permutations — Generate all permutations using backtracking. Handle duplicates and next permutation.
- Combination Sum — Find combinations that sum to target using backtracking. Handle reuse and duplicates.
- Word Search / Path Finding in Grid — Search for words in grid using backtracking. Handle visited cells and path restoration.
- N-Queens / Constraint Satisfaction — Solve N-Queens and Sudoku using backtracking with constraint propagation.
- Parentheses Generation — Generate all valid parentheses combinations using backtracking with balance tracking.
- Palindrome Partitioning — Partition string into palindromic substrings using backtracking.
Related DSA patterns
- Heap (Priority Queue) Patterns — Top K elements, K-way merge, two heaps for median, and scheduling.
- Greedy Patterns — Interval scheduling, jump games, stock trading, and task scheduling.
- Dynamic Programming (DP) Patterns — Fibonacci, Kadane, knapsack, LCS, LIS, edit distance, grid paths, and word break.
- Graph Traversal Patterns (DFS & BFS) — DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST.
Where to go next
Subsets (Include/Exclude) is one lesson in a 16-pattern DSA course. If you are preparing end to end, work the interview-critical patterns first and use the pattern sheet as the checklist; if you are here for one technique, the Backtracking Patterns guide is the shortest path back to the rest of it.