Python intuitive recursive solution


  • 1
    K

    I use recursive way to solve this problem.
    Like we have a array and a target value, if the array only contains 2 elements:a,b, we can obtain a+b,a-b,b-a,-a-b,ab,a/b,b/a .
    For 3 elements:a,b,c and target, we can try [a,b] and target+c,target-c, target
    c,target/c,c/target,c-target, note that when we want to multiply or divide by c , c can't be 0

            def solve(array,target):
                if len(array) == 2:
                    a,b = array
                    a *= 1.0
                    b *= 1.0
                    return abs(a+b - target) < 0.001 or abs(a*b - target) < 0.001 or abs(a/b - target) < 0.001 or abs(b/a - target) < 0.001 or abs(a-b - target) < 0.001 or abs(b-a - target) < 0.001 or abs(a+b + target) < 0.001 or abs(a*b + target) < 0.001 or abs(a/b + target) < 0.001 or abs(b/a + target) < 0.001
                elif len(array) == 3:
                    a,b,c = array
                    if solve([b,c],target+a) or solve([b,c],target-a) or (a != 0 and (solve([b,c],target*a) or solve([b,c],target/a) or solve([b,c],a/target))):
                        return True
                    if solve([a,c],target+b) or solve([a,c],target-b) or (b != 0 and (solve([a,c],target*b) or solve([a,c],target/b) or solve([a,c],b/target))):
                        return True
                    if solve([a,b],target+c) or solve([a,b],target-c) or (c != 0 and (solve([a,b],target*c) or solve([a,b],target/c) or solve([a,b],c/target))):
                        return True
                    return False
                else:
                    a,b,c,d = array
                    if solve([a,b,c],target+d) or solve([a,b,c],target-d) or (d != 0 and (solve([a,b,c],target*d) or solve([a,b,c],target/d) or solve([a,b,c],d/target))):
                        return True
                    if solve([a,b,d],target+c) or solve([a,b,d],target-c) or (c != 0 and (solve([a,b,d],target*c) or solve([a,b,d],target/c) or solve([a,b,d],c/target))):
                        return True
                    if solve([a,c,d],target+b) or solve([a,c,d],target-b) or (b != 0 and (solve([a,c,d],target*b) or solve([a,c,d],target/b) or solve([a,c,d],b/target))):
                        return True
                    if solve([b,c,d],target+a) or solve([b,c,d],target-a) or (a != 0 and (solve([b,c,d],target*a) or solve([b,c,d],target/a) or solve([b,c,d],a/target))):
                        return True
                    for i in xrange (3):
                        for j in xrange (i+1,4):
                            tmp_array = array[:i]+array[i+1:j]+array[j+1:]
                            tmp_i,tmp_j = array[i],array[j]
                            for tmp in (tmp_i+tmp_j,tmp_i*tmp_j,tmp_i*1.0/tmp_j,tmp_j*1.0/tmp_i,tmp_i-tmp_j,tmp_j-tmp_i):
                                if solve(tmp_array,target+tmp) or solve(tmp_array,target-tmp) or ( tmp != 0 and (solve(tmp_array,target*tmp) or solve(tmp_array,target/tmp))):
                                    return True
                    return False
            return solve(nums,24.0)
    

    Can anyone tell me the complexity? I am new to this... THX!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.