Backtrack

282. Expression Add Operator

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"] 

• 4 Operations: number extension, add, minus, multiple

• Record pre number for multiple operator to rollback

• First position only valid for add operator

• Number init with '0' is invalid

def addOperators(self, num: str, target: int) -> List[str]:
    self.ans = []
    self.backtrack(num, '', target, 0, 0, 0)
    return self.ans


def backtrack(self, num, express, target, idx, cur, pre):
    if idx == len(num):

        if cur == target:
            self.ans.append(express)
        return

    for end in range(idx+1, len(num)+1):
        # 01 is invalid
        if num[idx] == '0' and end > idx+1: break
        n = int(num[idx:end])

        # first index just has positive number
        if idx == 0:
            self.backtrack(num, str(n), target, end, n, n)
        else:
            self.backtrack(num, express+'+'+str(n), target, end, cur+n, n)
            self.backtrack(num, express+'-'+str(n), target, end, cur-n, -n)
            self.backtrack(num, express+'*'+str(n), target, end, cur-pre+n*pre, n*pre)

351. Android Unlock Pattern

Problem

1. add count by DFS

2. Build a skip matrix

3. Only not visit and (skip[i][j]==0 or visit[skip[i][j]] has visit, then go in recursion

def numberOfPatterns(self, m: int, n: int) -> int:
    self.skip = [[0] *10 for _ in range(10)]
    self.skip[1][3] = self.skip[3][1] = 2
    self.skip[1][7] = self.skip[7][1] = 4
    self.skip[3][9] = self.skip[9][3] = 6
    self.skip[7][9] = self.skip[9][7] = 8
    self.skip[1][9] = self.skip[9][1] = self.skip[3][7] = self.skip[7][3] = \
    self.skip[2][8] = self.skip[8][2] = self.skip[4][6] = self.skip[6][4] = 5
    
    res = 0
    visit = [False] * 10
    for i in range(m, n+1):
        res += self.dfs(visit, 1, i-1) * 4  # 1, 3, 7, 9 are symmetric
        res += self.dfs(visit, 2, i-1) * 4  # 2, 4, 6, 8 are symmetric
        res += self.dfs(visit, 5, i-1)    
    return res

def dfs(self, visit, p, remain):
    if remain == 0: return 1
    visit[p] = True
    res = 0
    for i in range(1, 10):
        if not visit[i] and (self.skip[p][i] == 0 or visit[self.skip[p][i]] == True):
            res += self.dfs(visit, i, remain-1)

    visit[p] = False
    return res