Backtracking LeetCode Problems: All 105,
With Python Solutions

Every problem in this library that LeetCode tags Backtracking. 86 of them carry a complete Python solution, a worked example and the time and space complexity of the approach.

Get Stealth Interview

Easy: 3
Medium: 71
Hard: 31

1 pattern

How Backtracking problems are solved

A tag names the subject, not the method. These pattern hubs cover the techniques that actually solve Backtracking problems — each one explains the approach, gives a Python template and states its complexity.

BacktrackingBuild candidates one choice at a time and abandon a branch the moment it cannot work.

Eyes only

When the Backtracking problem arrives live.

In the live round, Stealth Interview reads the problem off your screen, returns a working solution with a step-by-step explanation and its time and space complexity, and transcribes what the interviewer says. It's a desktop app for macOS and Windows, invisible to screen sharing.

Get Stealth Interview See pricing

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

Technical interview · 45 minsolution.pyShared editor · Python 3Longest substring without repeatsMediumGiven a string s, return the length of the longest contiguous substring in which every character is unique.s = "abcabcbb"
→ 31def length_of_longest_substring(s: str) -> int:2 last_seen = {}3 left = best = 04 for right, ch in enumerate(s):5 if ch in last_seen and last_seen[ch] >= left:

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 Terra

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

90%Subscription

python

Please analyze this context and help me answer the question or solve the problem.

python

def length_of_longest_substring(s: str) -> int:    last_seen = {}                    # char -> index    left = best = 0    for right, ch in enumerate(s):        if ch in last_seen and last_seen[ch] >= left:            left = last_seen[ch] + 1  # jump past it        last_seen[ch] = right        best = max(best, right - left + 1)    return best    last_seen = {}                    # char -> index

Approach

At each index r, the window's left edge is:

left r = max (left r -1, last[s r] + 1)

Time O(n): each character enters and leaves the window once.
Space O(min(n, k)): k is the size of the character set.

Type your message...

GPT-6.1 TerraClear chat

Primary display

QuitEscHide+QCapture+PCrop+OSubmit+EnterPress to get answerLeft/Right+Up/Down+

Backtracking problems by difficulty

Problems with a complete Python solution are listed first, then by ascending problem number.

Easy (3)

Easy problems
No.	Problem	Topics
0257	Binary Tree Paths	Tree, Depth-First Search, String +2
0401	Binary Watch	Bit Manipulation, Backtracking
1863	Sum of All Subset XOR Totals	Bit Manipulation, Array, Math +3

Medium (71)

Medium problems
No.	Problem	Topics
0017	Letter Combinations of a Phone Number	Hash Table, String, Backtracking
0022	Generate Parentheses	String, Dynamic Programming, Backtracking
0039	Combination Sum	Array, Backtracking
0040	Combination Sum II	Array, Backtracking
0046	Permutations	Array, Backtracking
0047	Permutations II	Array, Backtracking, Sorting
0077	Combinations	Backtracking
0078	Subsets	Bit Manipulation, Array, Backtracking
0079	Word Search	Depth-First Search, Array, String +2
0089	Gray Code	Bit Manipulation, Math, Backtracking
0090	Subsets II	Bit Manipulation, Array, Backtracking
0093	Restore IP Addresses	String, Backtracking
0095	Unique Binary Search Trees II	Tree, Binary Search Tree, Dynamic Programming +2
0113	Path Sum II	Tree, Depth-First Search, Backtracking +1
0131	Palindrome Partitioning	String, Dynamic Programming, Backtracking
0216	Combination Sum III	Array, Backtracking
0306	Additive Number	String, Backtracking
0357	Count Numbers with Unique Digits	Math, Dynamic Programming, Backtracking
0473	Matchsticks to Square	Bit Manipulation, Array, Dynamic Programming +2
0491	Non-decreasing Subsequences	Bit Manipulation, Array, Hash Table +1
0494	Target Sum	Array, Dynamic Programming, Backtracking
0526	Beautiful Arrangement	Bit Manipulation, Array, Dynamic Programming +2
0638	Shopping Offers	Bit Manipulation, Memoization, Array +3
0698	Partition to K Equal Sum Subsets	Bit Manipulation, Memoization, Array +3
0756	Pyramid Transition Matrix	Bit Manipulation, Hash Table, String +1
0784	Letter Case Permutation	Bit Manipulation, String, Backtracking
0797	All Paths From Source to Target	Depth-First Search, Breadth-First Search, Graph +1
0816	Ambiguous Coordinates	String, Backtracking, Enumeration
0842	Split Array into Fibonacci Sequence	String, Backtracking
0949	Largest Time for Given Digits	Array, String, Backtracking +1
0967	Numbers With Same Consecutive Differences	Breadth-First Search, Backtracking
0988	Smallest String Starting From Leaf	Tree, Depth-First Search, String +2
1079	Letter Tile Possibilities	Hash Table, String, Backtracking +1
1219	Path with Maximum Gold	Array, Backtracking, Matrix
1238	Circular Permutation in Binary Representation	Bit Manipulation, Math, Backtracking
1239	Maximum Length of a Concatenated String with Unique Characters	Bit Manipulation, Array, String +1
1286	Iterator for Combination	Design, String, Backtracking +1
1415	The k-th Lexicographical String of All Happy Strings of Length n	String, Backtracking
1593	Split a String Into the Max Number of Unique Substrings	Hash Table, String, Backtracking
1718	Construct the Lexicographically Largest Valid Sequence	Array, Backtracking
1774	Closest Dessert Cost	Array, Dynamic Programming, Backtracking
1849	Splitting a String Into Descending Consecutive Values	String, Backtracking, Enumeration
1947	Maximum Compatibility Score Sum	Bit Manipulation, Array, Dynamic Programming +2
1980	Find Unique Binary String	Array, Hash Table, String +1
1986	Minimum Number of Work Sessions to Finish the Tasks	Bit Manipulation, Array, Dynamic Programming +2
2002	Maximum Product of the Length of Two Palindromic Subsequences	Bit Manipulation, String, Dynamic Programming +2
2044	Count Number of Maximum Bitwise-OR Subsets	Bit Manipulation, Array, Backtracking +1
2048	Next Greater Numerically Balanced Number	Hash Table, Math, Backtracking +2
2178	Maximum Split of Positive Even Integers	Greedy, Math, Backtracking
2212	Maximum Points in an Archery Competition	Bit Manipulation, Array, Backtracking +1
2305	Fair Distribution of Cookies	Bit Manipulation, Array, Dynamic Programming +2
2375	Construct Smallest Number From DI String	Stack, Greedy, String +1
2397	Maximum Rows Covered by Columns	Bit Manipulation, Array, Backtracking +2
2597	The Number of Beautiful Subsets	Array, Hash Table, Math +4
2698	Find the Punishment Number of an Integer	Math, Backtracking
2708	Maximum Strength of a Group	Greedy, Bit Manipulation, Array +4
2767	Partition String Into Minimum Beautiful Substrings	Hash Table, String, Dynamic Programming +1
0254	Factor CombinationsPremium	Backtracking
0267	Palindrome Permutation IIPremium	Hash Table, String, Backtracking
0291	Word Pattern IIPremium	Hash Table, String, Backtracking
0294	Flip Game IIPremium	Memoization, Math, Dynamic Programming +2
0320	Generalized AbbreviationPremium	Bit Manipulation, String, Backtracking
0351	Android Unlock PatternsPremium	Bit Manipulation, Dynamic Programming, Backtracking +1
0681	Next Closest TimePremium	Hash Table, String, Backtracking +1
1066	Campus Bikes IIPremium	Bit Manipulation, Array, Dynamic Programming +2
1087	Brace ExpansionPremium	Stack, Breadth-First Search, String +2
1215	Stepping NumbersPremium	Breadth-First Search, Math, Backtracking
1258	Synonymous SentencesPremium	Sort, Union Find, Array +3
2152	Minimum Number of Lines to Cover PointsPremium	Bit Manipulation, Geometry, Array +5
2664	The Knight’s TourPremium	Array, Backtracking, Matrix
2992	Number of Self-Divisible PermutationsPremium	Bit Manipulation, Array, Math +4

Hard (31)

Hard problems
No.	Problem	Topics
0037	Sudoku Solver	Array, Hash Table, Backtracking +1
0051	N-Queens	Array, Backtracking
0052	N-Queens II	Backtracking
0126	Word Ladder II	Breadth-First Search, Hash Table, String +1
0140	Word Break II	Trie, Memoization, Array +4
0212	Word Search II	Trie, Array, String +2
0282	Expression Add Operators	Math, String, Backtracking
0301	Remove Invalid Parentheses	Breadth-First Search, String, Backtracking
0679	24 Game	Array, Math, Backtracking
0691	Stickers to Spell Word	Bit Manipulation, Memoization, Array +5
0773	Sliding Puzzle	Breadth-First Search, Memoization, Array +3
0980	Unique Paths III	Bit Manipulation, Array, Backtracking +1
0996	Number of Squareful Arrays	Bit Manipulation, Array, Hash Table +4
1096	Brace Expansion II	Stack, Breadth-First Search, Hash Table +3
1240	Tiling a Rectangle with the Fewest Squares	Backtracking
1255	Maximum Score Words Formed by Letters	Bit Manipulation, Array, Hash Table +5
1307	Verbal Arithmetic Puzzle	Array, Math, String +1
1467	Probability of a Two Boxes Having The Same Number of Distinct Balls	Array, Math, Dynamic Programming +3
1601	Maximum Number of Achievable Transfer Requests	Bit Manipulation, Array, Backtracking +1
1655	Distribute Repeating Integers	Bit Manipulation, Array, Dynamic Programming +2
1723	Find Minimum Time to Finish All Jobs	Bit Manipulation, Array, Dynamic Programming +2
1799	Maximize Score After N Operations	Bit Manipulation, Array, Math +4
2014	Longest Subsequence Repeated k Times	Greedy, String, Backtracking +2
2056	Number of Valid Move Combinations On Chessboard	Array, String, Backtracking +1
2065	Maximum Path Quality of a Graph	Graph, Array, Backtracking
2151	Maximum Good People Based on Statements	Bit Manipulation, Array, Backtracking +1
0411	Minimum Unique Word AbbreviationPremium	Bit Manipulation, Array, String +1
0425	Word SquaresPremium	Trie, Array, String +1
0465	Optimal Account BalancingPremium	Bit Manipulation, Array, Dynamic Programming +2
0489	Robot Room CleanerPremium	Backtracking, Interactive
1088	Confusing Number IIPremium	Math, Backtracking

How Backtracking problems are solved

When the Backtracking problem arrives live.

Approach

Approach

Approach

Backtracking problems by difficulty

Easy (3)3

Medium (71)71

Hard (31)31

Keep exploring

Easy (3)

Medium (71)

Hard (31)