Backtrack: Find target using '+', '-', '*', '/'

Posted on | In | Comments: | Views:

I. What

Given an list of number (no ‘0’) and a target, combined with any operator from +, -, *, /, check if they can form into an formular which evaluated to be target.

example:

  1. Array: [4, 2, 3, 1, 5, 6]
  2. target: 10
  3. should return true, as [1, "+", 5, "+", 6, "+", 4, "-", 2, "*", 3] = 10

II. Analysis

try to put each element to be the n-th operand, followed by each operator as a potential prefix as follows:

1
2
3
4
							1						2						3						4						5
				+ 	 -  	*  	/
		 2 3 4 5
+ - * /

III. Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, t) {
    let visited = new Set();
    let len = nums.length;
    let prefix = [];
    let symbols = ['+', '-', '*', '/'];
    
    function helper(prefix) {
        if (prefix.length === 2 * len) {
            let res = evaluate(prefix, t) 
            console.log(prefix);
            console.log(res);
            return res === t;
        }
        
        for (let i = 0; i < len; i++) {
            if (!visited.has(i)) {
                visited.add(i);
                prefix.push(nums[i]);
                for (let j = 0; j < 4; j++) {
                    prefix.push(symbols[j]);
                    if (helper(prefix)) {
                        return true;
                    }
                    prefix.pop()
                }
                prefix.pop();
                visited.delete(i);
            }
        }
        return false;
    }
  
    return helper(prefix);
    
    // evaluate such arr [1, "+", 5, "+", 6, "+", 4, "-", 2, "*", 3, "+"]
    function evaluate(prefix) {
        prefix[prefix.length - 1] = '+';
        let operator = [];
        let operand = [];
        
        operand.push(0);
        operator.push('+');
        operand.push(prefix[0]);
      
        for (let i = 1; i < prefix.length; i += 2) {
            let symbol = prefix[i]
            let digit = prefix[i + 1];
            let lastSymbol = operator[operator.length - 1];
            if (compare(symbol, lastSymbol) > 0) {
                let digitPre = operand.pop();
                operand.push(evaluate(digitPre, symbol, digit));
            } else {
                let symbolPre = operator.pop();
                let digit2 = operand.pop();
                let digit1 = operand.pop();
                operand.push(evaluate(digit1, symbolPre, digit2));
                operand.push(digit);
                operator.push(symbol);
            }
        }
        operand.pop()
        return operand.pop();
        
        function evaluate(d1, s, d2) {
            switch (s) {
                case '+': return d1 + d2;
                case '-': return d1 - d2;
                case '*': return d1 * d2;
                case '/': return d1 / d2;
                default: return null;
            }
        }
    }
    
    
  	// compare operator priority
    function compare(s1, s2) {
        return evaluate(s1) - evaluate(s2);
        function evaluate(s) {
            if (s === '*' || s === '/') {
                return 1;
            }
            return 0;
        }   
    }
};

let nums = [1, 5, 6, 2, 3, 4];
let target = 10;
let res = findTargetSumWays(nums, target);

console.log(res);