Backtracking

Backtracking recursion

Build up many possible solutions through multiple recursive calls at each step

Seed the initial recursive call with an “empty” solution

At each base case, you have a potential solution

choose/explore/unchoose pattern

General approach to backtracking problems like subsets, permutation and combination sums. Link

public void backtracking(finalResult, tempResult /* some parameters*/) {
    // base case
    if (/* something */) {
        finalResult.add(tempResult);
    } else {
        for (int i = 0; i < /* problem param */; i++) {
            tempResult.add(/*... eg: nums[i]*/);
            backtracking(finalResult, tempResult, /* remaining solution */ );
            tempResult.remove(/*last item*/);
        }
    }
}

public void mainProblem(/* problem parameters */) {
    backtracking(finalResult, tempResult /* some parameters initialized to 0*/)
    return finalResult;
}

Example: Generate Subsets

def subsets(self, nums: List[int]) -> List[List[int]]:
        finalResult = []
        def backtrack(tempResult, nums, start):
            finalResult.append(tempResult)
            for i in range(start, len(nums)):
                backtrack(tempResult + [nums[i]], nums, i+1)      
        backtrack([], sorted(nums), 0)
        return finalResult

Alternatively: one-liners

def subsets(self, nums):
    [l for n in range(len(nums) + 1) for l in itertools.combinations(nums, n)]

# or
def subsets(self, nums): # I can't understand this clearly :(
    return functools.reduce(lambda L, ele: L + [l + [ele] for l in L], nums, [[]])

Problems

  1. Letter Combinations of a Phone Number
  2. Generate Parentheses
  3. Permutations
  4. Combination sum
  5. Subsets
  6. Palindrome Partitioning
Written on July 25, 2019