num_equation

num_equation.py

'''
Given integer array and integer k, return all possible equation that array can be calculated to k.
Operations can be +, -, *, /, ()

1. searchRecursive is the solution that the relative position of array can not be changed
2. search2Recursive is the solution that the relative position can be changed
'''


'''
The idea is use backtracking method to iterate through all the possible expressions.
nums represent the remaining nums to be calculated
exprs represent the calculated expressions

in each iteration:
1. choose num(i) and another num(j)
2. iterate through every operations
3. do the caclculation as c(a+b), than add c to nums and add expr to exprs
4. if len nums is 1 and nums[0] is k, add it to the result
'''


def calculate(a, b, op):
    if op == '+':
        return a+b
    elif op == '-':
        return a-b
    elif op == '*':
        return a*b
    else:
        return a/b


# should maintain the relative position of nums
# nums can only be chosen between to each other
def searchRecursive(res, nums, exprs, k):
    if len(nums) == 1:
        if nums[0] == k:
            res.append(exprs[0])
        return
    for i in range(len(nums)-1):
        a, b = nums[i], nums[i+1]
        exp1, exp2 = exprs[i], exprs[i+1]
        copyNums = list(nums[:i+1]+nums[i+2:])
        copyExprs = list(exprs[:i+1]+exprs[i+2:])
        for op in ['+', '-', '*', '/']:
            if b != 0 or (b == 0 and op != '/'):
                c = calculate(a, b, op)
                expr = '(' + exp1 + op + exp2 + ')'
                copyNums[i] = c
                copyExprs[i] = expr
                searchRecursive(res, copyNums, copyExprs, k)


# nums that can be chosen at any position
def search2Recursive(res, nums, exprs, k, n):
    if n == 1:
        if nums[0] == k:
            res.append(exprs[0])
        return
    for i in range(n-1):
        a, exp1 = nums[i], exprs[i]
        for j in range(i+1, n):
            b, exp2 = nums[j], exprs[j]
            nums[j] = nums[n-1]
            exprs[j] = exprs[n-1]
            for op in ['+', '-', '*', '/']:
                if b != 0 or (b == 0 and op != '/'):
                    c = calculate(a, b, op)
                    expr = '(' + exp1 + op + exp2 + ')'
                    nums[i] = c
                    exprs[i] = expr
                    # print exprs, nums
                    search2Recursive(res, nums, exprs, k, n-1)
            nums[j], exprs[j] = b, exp2
        nums[i], exprs[i] = a, exp1


nums = [1, 5, 2, 3]
k = 24
exprs = map(str, nums)
res1, res2 = [], []
searchRecursive(res1, nums, exprs, k)
print res1
search2Recursive(res2, nums, exprs, k, len(nums))
print res2