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

Problem Description:

Given an integer array nums that may contain duplicates, 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,2]
Output: [[],[1],[1,2],[1,2,2],[2],[2,2]]

Solution:

def subsetsWithDup(nums):
    result = []
    nums.sort() # make sure to sort nums to find duplicates easier
    
    def dfs(start_index, state):
        result.append(state[:]) 

        for i in range(start_index, len(nums)):
            # avoid duplicates with deduplication
            if i > start_index and nums[i] == nums[i - 1]: 
                continue
            
            state.append(nums[i])
            dfs(i + 1, state)
            state.pop() 

    dfs(0, [])
    return result 

Combinations II

Problem Description:

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.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

Solution:

def combinationSum2(nums, target):
    result = []
    nums.sort() # make sure to sort nums to find duplicates easier
    def dfs(start_index, state, remaining):
        if remaining == 0:
            result.append(state[:])
            return
        elif remaining < 0: 
            return

        for i in range(start_index, len(nums)):
            # avoid duplicates
            if i != start_index and nums[i] == nums[i-1]: 
                continue

            state.append(nums[i])
            dfs(i + 1, state, remaining - nums[i])
            state.pop()

    dfs(0, [], target)
    return result

Permutations II

Problem Description:

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

Example 1:

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

Solution:

def permuteUnique(nums):
    used = [False] * len(nums)
    result = []
    nums.sort() #sort nums
    
    def dfs(start_idx, state):
        if start_idx == len(nums):
            result.append(state[:])
            return
        
        for i in range(0, len(nums)):
            if used[i]: 
                continue
            # avoid duplicates
            if(i > 0 and nums[i] == nums[i-1] and not used[i-1]): 
                continue
 
            state.append(nums[i])
            used[i] = True
            dfs(start_idx + 1, state)
            used[i] = False
            state.pop()
    
    dfs(0, [])
    return result

---

Pruning

Practice Problems

Generate all Valid Parenthesis

def generateParenthesis(n):
    result = []
    def dfs(start_idx, state, oCount, cCount):
        if start_idx == n*2:
            result.append("".join(state))
            return
        
        if oCount < n:
            state.append('(')
            dfs(start_idx + 1, state, oCount + 1, cCount )
            state.pop()

        if cCount < oCount:
            state.append(')')
            dfs(start_idx + 1, state, oCount, cCount + 1)
            state.pop
    
    dfs(0, [], 0, 0)
    return result

Partition a String into Palindromes

def partition(s):
    result = []

    n = len(s)
    def is_palindrome(word):
        return word == word[::-1] #reverse

    def dfs(start_idx, state):
        if start_idx == n:
            result.append(state[:])
            return

        for i in range(start_idx + 1, n + 1):
            prefix = s[start_idx: i]
            if is_palindrome(prefix):
                dfs(i, state + [prefix])

    dfs(0, [])
    return result

---

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

 def numDecodings(s):
    memo = {}
    def dfs(start_idx, memo):
        if start_idx in memo:
            return memo[start_idx]
            
        if start_idx == len(s):
            return 1
        
        ways = 0

        # can't decode string with leading 0
        if s[start_idx] == '0':
            return ways
        
        # decode one digit
        ways += dfs(start_idx + 1, memo)
        
        #decode two digits, number has to be between 10 and 26
        if 10 <= int(s[start_idx: start_idx + 2]) <= 26:
            ways += dfs(start_idx + 2, memo)

        memo[start_idx] = ways
        return ways

    return dfs(0, memo)

Word Break

def word_break(s, words):
    memo = {}

    def dfs(start_index):

        if start_index in memo:
            return memo[start_index]

        if start_index == len(s):
            return True

        result = False
        for word in words:
            if s[start_index:].startswith(word):
                if dfs(start_index + len(word)):
                    result = True
                    break

        memo[start_index] = result
        return result

    return dfs(0)

Min Number of Coins

def coinChange(coins, amount):
    result =_coinChange(coins, amount, {})
    if result == float('inf'):
        return -1
    else:
        return result

def _coinChange(coins, amount, memo):
    if amount in memo:
        return memo[amount]
    
    if amount < 0:
        return float('inf')
    
    if amount == 0:
        return 0
    
    min_coins = float('inf')
    
    for coin in coins:
        num_coins = 1 + _coinChange(coins, amount - coin, memo)
        min_coins = min(min_coins, num_coins)
    
    memo[amount] = min_coins
    return min_coins