Category: backtracking
-
LeetCode 39: Combination Sum
link Backtracking For each element , we take instances of it such that and try to make using other elements. We process candidates in a sorted order to be able to use a set to keep only unique combinations. Recursion tree has height and width . So, time: , space: . Dynamic programming Subproblem Let…
-
LeetCode 473: Matchsticks to Square
link Adding up the matchsticks gives the square’s and the square’s expected side length is . Now, using all the matchsticks exactly once, we need to build the four sides–each side must have the expected length. Backtracking From a side’s point of view We try making one side at a time using all combinations of…
-
LeetCode 37: Sudoku Solver
link We collect all empty cells in a list and try filling them up using only the currently available digits for that cell. As a pre-processing step, we also populate (and later use): A digit is available for the empty cell (row, col) only if none of the above three contains the digit. If there…
-
LeetCode 465: Optimal Account Balancing
link We can summarize all transactions as balances per person. In the end, there might be positive balances and negative balances, but they must sum up to 0. Blind alleys What works Try matching each positive balance with each negative balance making sure a transaction does not change a positive balance to negative or a…
-
LeetCode 401: Binary Watch
link We can generate hours and minutes separately and take their Cartesian product to create valid times. For a given number of turned on hour (or minute) bits, we generate subsets of hour (or minute) bits. Time: , space: .
-
LeetCode 2850: Minimum Moves to Spread Stones Over Grid
link The problem restricts placing one stone per move, otherwise it would have been harder. The problem here is to find the minimum total cost of assigning every empty cell to one extra stone. The cost of one such assignment is the Manhattan distance between the empty cell and the stone’s cell. We construct a…
-
LeetCode 733: Flood Fill
link If source color and target color are the same, nothing to do. Otherwise, we remember the source color, color the cell and its four neighbors. A cell is filled at most once. Time: , space: .
-
LeetCode 93: Restore IP Addresses
link With the 3 dots inserted, the length of a valid ip address is len(s)+3. We create different possible four-parts via backtracking and include the valid ones. Time: , space: .
-
LeetCode 79: Word Search
link We try finding the word one character at a time starting from every cell avoiding already visited cells. Say . Time: , space: . Follow up: Could you use search pruning to make your solution faster with a larger board? We start searching with a word character that appears the least in the board, in that…
unreasonably effective 