282. Expression Add Operators

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.

Examples:

"123", 6 -> ["1+2+3", "1*2*3"]
"232", 8 -> ["2*3+2", "2+3*2"]
"105", 5 -> ["1*0+5","10-5"]
"00", 0 -> ["0+0", "0-0", "0*0"]
"3456237490", 9191 -> []

my accepted code can be found here

I don’t find any tricks in this problem, and tried a brute force DFS here. The efficiency of the algorithm turns out acceptable if we try to avoid copying of string as much as possible (beats 97%).

So basically we try every possible operator at every possible position, and deal with the edge case of leading 0 and the operator precedence correctly. Details are explained in the algorithm below:

ExpressionAddOperators(num: string, target: int): string[]:
    let result = empty array of string
    let accSeq = empty array of integer
    for i = 1 to length(num):
        let firstNum = strToInt(num[0 until i])
        append(accSeq, firstNum)
        DFS(acc, accSeq, num, i, firstNum, opToInt('+'), result, target)
        pop(accSeq)
    return result

// acc: accumulated result before position `pos`
// accSeq: accumulated sequence forming expression (number (op number)*)
// num: the input number string
// pos: start of the next number
// lastOp: last operator before the last term, used for dealing with operator precedence
// lastTerm: last term, used for dealing with operator precedence
// result: final result
// target: target result
DFS(acc: int, accSeq: int[], num: string, pos: int, lastOp: Operator, lastTerm: int, result: string[], target: int):
    // base case
    if acc == target and pos == length(num):
        append(result, seqToString(accSeq))
        return
    for i = pos + 1 to length(num):
        let nextNum = strToInt(num[pos until i])
        for op = {'+', '-', '*'}:
            append(accSeq, op)
            append(accSeq, nextNum)

            if op is '*':
                newAcc = if lastOp is '+'
                    then acc - lastTerm + lastTerm * nextNum
                    else acc + lastTerm - lastTerm * nextNum
                newLast = nextNum * lastTerm
                newOp = lastOp
            else if op is '+'
                newAcc = acc + nextNum
                newOp = '+'
                newLast = nextNum
            else if op is '-'
                newAcc = acc - NextNum
                newOp = '-'
                newLast = nextNum

            dfs(newAcc, accSeq, num, i, newOp, newLast, result, target)

            // back track
            pop(accSeq)
            pop(accSeq)

We handle the problem of operator precedence in a brute force way, we remember the result and operator immediately before the last consecutive multiplications. And if next operator we have is still a multiplication, we recalculate the accumulated result according to that information.

The time complexity seems to be exponential, and space is approximately O(N) with N being the length of the number.

330. Patching Array

Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

nums = [1, 3], n = 6

Return 1.

Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.

Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].

Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6]. So we only need 1 patch.

Example 2:

nums = [1, 5, 10], n = 20

Return 2.

The two patches can be [2, 4].

Example 3:

nums = [1, 2, 2], n = 5

Return 0.

my accepted code can be found here

This problem, however, is solved by a trick. We record the upperbound, the numbers below with can be formed by the sum of some elements of the array. We scan the sorted array in an ascending order, and if the element we met is within the bound, we don’t need to add any number to the array, and the bound can be extended by the amount of the number we met (since every number below the bound can be formed); otherwise, we add the number of the upperbound into the array, and can be extended likewise, we continue the process until the target is reached.

MinPatch(a: int[], target: int): int:
    let result = 0
    let bound = 1
    let i = 0
    for bound <= target:
        if i < length(a) and a[i] <= bound:
            bound += a[i]
            i = i + 1
        else:
            bound = bound + bound
            result = result + 1
    return result

The time complexity is O(n) worst case, and extra space is O(1)