backtracking + misc Flashcards
Given an integer array nums of unique elements, return all possible subsets.
standard backtracking; we proceed with both path 1 - include current num, and path 2 - don’t include current num. no for loop
time: O(n * 2^n)
2^(n - 1) subsets, and O(n) to copy each subset into output.
space: O(n)
Given an array of distinct ints and a target, return a list of all unique combinations of nums where the chosen nums sum to target. The same number may be chosen from candidates an unlimited number of times
remember to check for valid sum conditions. we pursue 2 paths: 1 - add current num again, 2 - don’t add current num and move onto the next num
time: we make 2 decisions at each step, and worst case, the height of our tree is == target, if all nums are 1. O(2 ^ target)
space: O(n)
https://leetcode.com/problems/combinations/
Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].
include the num or don’t include it
time: at most n decisions at each step (but most steps have less), height of tree is k, O(k) time to copy each combination. loose upper bound is O(k * n^k)
space: O(k)
Given an array nums of distinct integers, return all the possible permutations.
use a set and start for-loop at 0 every time. skip num if it’s in the set. add to set, add to temp. after rec call, remove
time: O(n * n!); space: O(n)
Given an integer array nums that may contain duplicates, return all possible subsets.
same as subsets 1 but SORT and add this line: if i != idx and nums[i] == nums[i - 1], continue
time: O(n * 2^n)
space: O(n)
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in (candidates) where the candidate numbers sum to (target).
SORT the input array and do
i != idx and nums[i] == nums[i - 1], continue
time: O(n * 2^n)
space: O(n)
Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.
instead of iterating thru input array, create map { num: count } and iterate thru its keyset instead.
if num’s count == 0, continue. and then go down the 2 paths, remember to update map each time
time: O(n * n!)
space: O(n)
https://leetcode.com/problems/restore-ip-addresses/description/
- impossible if len == 0 or len == 12
- recursive function: return when there are too many chars left in string
- for loop thru nums 1 to 3; these are the nums you add to sIdx to get the substring you’re currently considering. (return if sIdx + i > s.length()). must consider num == 0 separately since no leading 0s allowed (call helper and break)
TC: we need to separate the input string into 4 integers, each integer is at most 3 digits. O(4 * 3^4)
https://leetcode.com/problems/partition-to-k-equal-sum-subsets/
TC: O(k * 2^n). either we include the num, or we don’t include it; that’s 2^(n - 1). we must generate k subsets.
if k == 0 return true;
if currSum == goalSum, call helper(), but with idx = 0.
maintain a used[] array to keep track of which nums have been used.
https://leetcode.com/problems/letter-combinations-of-a-phone-number/description/
O(n * 4^n)
https://leetcode.com/problems/splitting-a-string-into-descending-consecutive-values/description/
pass in a ‘prev’ variable to the helper function. handle the cases prev == null and prev == curr + 1 separately. also maintain a count variable; it must be at least 2
better than O(n ^ n) since we’ll be pruning
https://leetcode.com/problems/palindrome-partitioning/description/
TC: there are n-1 places we can cut a string of length n. at each of those places, we can cut or not cut. it also costs O(n) to copy and add each substring into the output. so TC is O(n * 2^n)
use helper isPal() function to build a boolean[][] array of palindromicities. use a standard backtracking helper function
https://leetcode.com/problems/matchsticks-to-square/
exact same concept as partition into k equal sum subsets
TC: O(4^n). height of tree is n, and at each level we make 4 decisions.
https://leetcode.com/problems/maximum-length-of-a-concatenated-string-with-unique-characters/
either we include the string, or we don’t include it.
use hasUniqueChars helper function for the concatenated string.
TC: O(2^n * m), where m is avg length of each string, and n is the number of strings.
https://leetcode.com/problems/n-queens/description/
placements[] array for rows and 3 sets for col, diag1 (r + c), diag2 (r - c).
if row == n, build board and add to output.
for loop (cols) 0 to n - 1. if value is in one of the 3 sets, continue. else, set placements[row] = col, add values to sets, and make a recursive call. then, backtrack by erasing the placement and deleting from all 3 sets
TC: with each row, we have a few less choices to place the queen in. upper bound O(n!)
