Backtracking

Backtracking

Fifty questions on backtracking, for generating combinations, permutations, and constraint-satisfaction solutions.

Get All Root-to-Leaf Paths

easy
Return every root-to-leaf path in a binary tree as a list of node values, instead of an arrow-joined string.

Binary Tree Paths

easy
Return every root-to-leaf path in a binary tree as an arrow-joined string.

Binary Watch

easy
A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59).

Sum of All Subset XOR Totals

easy
The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty.

Additive Number

medium
An additive number is a string whose digits can form an additive sequence.

All Paths From Source to Target

medium
Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n - 1, find all possible paths from node 0 to node n - 1 and return them in any order.

Ambiguous Coordinates

medium
We had some 2-dimensional coordinates, like "(1, 3)" or "(2, 0.5)".

Beautiful Arrangement

medium
Suppose you have n integers labeled 1 through n.

Circular Permutation in Binary Representation

medium
Given 2 integers n and start.

Closest Dessert Cost

medium
You would like to make dessert and are preparing to buy the ingredients.

Combination Sum

medium
Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target.

Combination Sum III

medium
Find all valid combinations of k numbers that sum up to n such that the following conditions are true: Return a list of all possible valid combinations.

Combinations

medium
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

Construct Smallest Number From DI String

medium
You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

Construct the Lexicographically Largest Valid Sequence

medium
Given an integer n, find a sequence with elements in the range [1, n] that satisfies all of the following: The distance between two numbers on the sequence, a[i] and a[j], is the...

Count Number of Maximum Bitwise-OR Subsets

medium
Given an integer array nums, find the maximum possible bitwise OR of a subset of nums and return the number of different non-empty subsets with the maximum bitwise OR.

Count Numbers with Unique Digits

medium
Given an integer n, return the count of all numbers with unique digits, x, where 0 <= x < 10n.

Fair Distribution of Cookies

medium
You are given an integer array cookies, where cookies[i] denotes the number of cookies in the ith bag.

Find the Punishment Number of an Integer

medium
Given a positive integer n, return the punishment number of n.

Find Unique Binary String

medium
Given an array of strings nums containing n unique binary strings each of length n, return a binary string of length n that does not appear in nums.

Generate Binary Strings Without Adjacent Zeros

medium
You are given a positive integer n.

Generate Parentheses

medium
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Gray Code

medium
An n-bit gray code sequence is a sequence of 2n integers where: Given an integer n, return any valid n-bit gray code sequence.

Largest Time for Given Digits

medium
Given an array arr of 4 digits, find the latest 24-hour time that can be made using each digit exactly once.

Letter Case Permutation

medium
Given a string s, you can transform every letter individually to be lowercase or uppercase to create another string.

Letter Combinations of a Phone Number

medium
Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

Letter Tile Possibilities

medium
You have n tiles, where each tile has one letter tiles[i] printed on it.

Matchsticks to Square

medium
You are given an integer array matchsticks where matchsticks[i] is the length of the ith matchstick.

Maximum Compatibility Score Sum

medium
There is a survey that consists of n questions where each question's answer is either 0 (no) or 1 (yes).

Maximum Length of a Concatenated String with Unique Characters

medium
You are given an array of strings arr.

Maximum Points in an Archery Competition

medium
Alice and Bob are opponents in an archery competition.

Maximum Product of the Length of Two Palindromic Subsequences

medium
Given a string s, find two disjoint palindromic subsequences of s such that the product of their lengths is maximized.

Maximum Rows Covered by Columns

medium
You are given an m x n binary matrix matrix and an integer numSelect.

Maximum Split of Positive Even Integers

medium
You are given an integer finalSum.

Maximum Strength of a Group

medium
You are given a 0-indexed integer array nums representing the score of students in an exam.

Minimum Number of Work Sessions to Finish the Tasks

medium
There are n tasks assigned to you.

Minimum Time to Break Locks I

medium
Bob is stuck in a dungeon and must break n locks, each requiring some amount of energy to break.

Next Greater Numerically Balanced Number

medium
An integer x is numerically balanced if for every digit d in the number x, there are exactly d occurrences of that digit in x.

Non-decreasing Subsequences

medium
Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements.

Numbers With Same Consecutive Differences

medium
Given two integers n and k, return an array of all the integers of length n where the difference between every two consecutive digits is k.

Palindrome Partitioning

medium
Given a string s, partition s such that every substring of the partition is a palindrome.

Partition String Into Minimum Beautiful Substrings

medium
Given a binary string s, partition the string into one or more substrings such that each substring is beautiful.

Partition to K Equal Sum Subsets

medium
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.

Path with Maximum Gold

medium
In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty.

Permutations

medium
Given an array nums of distinct integers, return all the possible permutations.

Permutations II

medium
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Restore IP Addresses

medium
A valid IP address consists of exactly four integers separated by single dots.

Shopping Offers

medium
In an online store, there are n items to sell.

Split a String Into the Max Number of Unique Substrings

medium
Given a string s, return the maximum number of unique substrings that the given string can be split into.

Split Array into Fibonacci Sequence

medium
You are given a string of digits num, such as "123456579".