DSA: Backtracking

Backtracking Template

Subsets

Combinations

Permutations

Deduplication

Subsets II

Combinations II

Permutations II

Pruning

Practice Problems

Memoization

Practice Problems

---

Backtracking Template

Backtracking is essentially a way of depth first search but is very useful when it comes to solving problems regarding subsets, combinations, and permutations.

Below is a base template you can use to help solve backtracking problems:

def solution(input):
# Add edge cases if any
  
# Global Variable
  result = []

# Sort or add a hashMap if necessary
  input = input.sort()
 
#Recursive Depth First Search Helper Function
  def dfs(start_idx, state):
#   Backtracking Case if any: 
#   Makes it so that you don't have to check certain constraints if the value is larger than your target

#   Base Case: 
    if start_idx == len(input):
      # create a copy of the state
      result.append(state[:]) 
      # Use ''.join(state) if string
      return
  
#   DFS Recursive Case
    for i in range(start_idx, len(input)):
      state.append(input[i]) #Add to state
      dfs(i + 1, input, state)
      state.pop() #backtrack
      
#   Call the DFS function and return result
  dfs(0, [])

  return result

---

Subsets

Subsets I

Problem Description:

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Solution:

def subsets(nums):
    res = []
    def dfs(start_idx, state):
        # add a copy of the state to the result
        res.append(state[:])

        for i in range(start_idx, len(nums)):
            state.append(nums[i])
            dfs(i + 1, state)
            state.pop() #backtrack

    dfs(0, [])
    return res
    

*Note: If you increment the dfs function with the start_idx, you will get a different result where your result will double count values. Make sure to use i + 1 instead of start_idx + 1.*

Time Complexity: O(2^n)

Space Complexity: O(2^n)

Leetcode: Subsets - LeetCode

---

Combinations

Combinations I

Problem Description:

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. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]

Solution:

def combinationSum(candidates, target):
    result = []

    def dfs(start_idx, remaining, state):
        if remaining == 0:
            result.append(state[:])
            return
        # avoid results exceeding target
        elif remaining < 0:
            return

        for i in range(start_idx, len(candidates)):
            #add the number into the combination
            state.append(candidates[i])
            
            #give the current number another chance, rather than moving on
            dfs(i, remaining - candidates[i], state)
            
            #backtrack, remove the number from the combination
            state.pop()

    dfs(0, target, [])

    return result

Time Complexity: O(n^target/min(candidates)). In the worse case, the state-space tree has n branches and the depth of the tree is at most target divided by the smallest number in candidates.

Leetcode: Combination Sum - LeetCode

---

Permutations

Permutations I

Problem Description:

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Solution:

def permute(nums):
    result = []
    used = [False] * len(nums)

    def dfs(start_index, state, used):
        if start_index == len(nums):
            result.append(state[:])
            return

        for i, num in enumerate(nums):
            # skip used nums
            if used[i]:
                continue
            # add num to permutation, mark num as used
            
            state.append(num)
            used[i] = True
            dfs(start_index + 1, state, used)
            # remove num from permutation, mark num as unused
            state.pop()
            used[i] = False

    dfs(0, [], used)
    return result

Time Complexity: We have n letters to choose in the first level, n - 1 choices in the second level and so on therefore the number of operation is n * (n - 1) * (n - 2) * ... * 1, or O(n!)

Leetcode: Permutations - LeetCode

---

Deduplication

Deduplication is the process of eliminating duplicate or redundant information, especially in computer data

Let's take a look at the following problems if there were duplicate values involved:

Subsets II

Combinations II

Permutations II

---

Pruning

Practice Problems

Generate all Valid Parenthesis

Partition a String into Palindromes

---

Memoization

Memoization is a fancy word for a simple concept (so is the case for a lot of things we learn in school). It means saving the previous function call result in a dictionary and reading from it when we do the exact same call again. And no I didn't spell it wrong. The word is meant to mean writing down on a "memo".

Practice Problems

Decode Ways

Word Break

Min Number of Coins