Question

Formatted question description: https://leetcode.ca/all/282.html

Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.

Note that operands in the returned expressions should not contain leading zeros.

Example 1:

Input: num = "123", target = 6
Output: ["1*2*3","1+2+3"]
Explanation: Both "1*2*3" and "1+2+3" evaluate to 6.

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2","2+3*2"]
Explanation: Both "2*3+2" and "2+3*2" evaluate to 8.

Example 3:

Input: num = "3456237490", target = 9191
Output: []
Explanation: There are no expressions that can be created from "3456237490" to evaluate to 9191.

Constraints:

1 <= num.length <= 10
num consists of only digits.
-2³¹ <= target <= 2³¹ - 1

Algorithm

We need two variables diff and sumUpToPrevNum, one is used to record the value to be changed, the other is the value after the current operation, and they all need to use long type, because the string is converted to int type, it is easy to overflow.

For addition and subtraction, diff is the negative value of the number to be added and the number to be subtracted.

For multiplication, it’s a bit more complicated, diff is the diff of the last change multiplied by the number to be multiplied.

For example, for example, 2+3*2, when the calculation is about to multiply by 2, the last cycle of sumUpToPrevNum = 5, diff = 3, and if we want to calculate this multiplication by 2, the new change value diff should It is 32=6, and we need to remove the result of the previous +3 operation, and add a new diff, namely (5-3)+6=8, which is the value of the new expression 2+32.

Another thing to note is that if the input is “000”, 0, the following errors are prone to occur:

Wrong: ["0+0+0","0+0-0","0+0*0","0-0+0","0-0-0","0-0*0" ,"0*0+0","0*0-0","0*0*0","0+00","0-00","0*00","00+0"," 00-0","00*0","000"]

Correct:["0*0*0","0*0+0","0*0-0","0+0*0","0+0+0","0+0-0" ,"0-0*0","0-0+0","0-0-0"]

Code

import java.util.ArrayList;
import java.util.List;

public class Expression_Add_Operators {

    class Solution {

        public List<String> addOperators(String num, int target) {

            ArrayList<String> result = new ArrayList<String>();

            if (num.length() == 0) {
                return result;
            }

            dfs(num, target, 0, 0, "", result);

            return result;
        }

        // `diff` is for rollback previous `*` operation
        void dfs(String digitString, int target, long diff, long sumUpToPrevNum, String oneResult, ArrayList<String> res) {

            if (digitString.length() == 0 && sumUpToPrevNum == target) {
                res.add(oneResult);
                return;
            }

            for (int i = 1; i <= digitString.length(); ++i) {

                // divide and conquer
                String cur = digitString.substring(0, i);
                String next = digitString.substring(i);

                if (cur.length() > 1 && cur.charAt(0) == '0') { // @note: skip '000', but single '0' is ok
                    return;
                }

                if (oneResult.length() > 0) {
                    dfs(next, target, Long.valueOf(cur), sumUpToPrevNum + Long.valueOf(cur), oneResult + "+" + cur, res);
                    dfs(next, target, -1 * Long.valueOf(cur), sumUpToPrevNum - Long.valueOf(cur), oneResult + "-" + cur, res);
                    dfs(next, target, diff * Long.valueOf(cur), (sumUpToPrevNum - diff) + diff * Long.valueOf(cur), oneResult + "*" + cur, res);
                } else {
                    dfs(next, target, Long.valueOf(cur), Long.valueOf(cur), cur, res); // use `cur` as oneResult
                }
            }
        }
    }
}

############


class Solution {
    private List<String> ans;
    private String num;
    private int target;

    public List<String> addOperators(String num, int target) {
        ans = new ArrayList<>();
        this.num = num;
        this.target = target;
        dfs(0, 0, 0, "");
        return ans;
    }

    private void dfs(int u, long prev, long curr, String path) {
        if (u == num.length()) {
            if (curr == target) ans.add(path);
            return;
        }
        for (int i = u; i < num.length(); i++) {
            if (i != u && num.charAt(u) == '0') {
                break;
            }
            long next = Long.parseLong(num.substring(u, i + 1));
            if (u == 0) {
                dfs(i + 1, next, next, path + next);
            } else {
                dfs(i + 1, next, curr + next, path + "+" + next);
                dfs(i + 1, -next, curr - next, path + "-" + next);
                dfs(i + 1, prev * next, curr - prev + prev * next, path + "*" + next);
            }
        }
    }
}

class Solution {
public:
    vector<string> addOperators(string num, int target) {
        vector<string> res;
        helper(num, target, 0, 0, "", res);
        return res;
    }
    void helper(string num, int target, long diff, long curNum, string out, vector<string>& res) {
        if (num.size() == 0 && curNum == target) {
            res.push_back(out); return;
        }
        for (int i = 1; i <= num.size(); ++i) {
            string cur = num.substr(0, i);
            if (cur.size() > 1 && cur[0] == '0') return;
            string next = num.substr(i);
            if (out.size() > 0) {
                helper(next, target, stoll(cur), curNum + stoll(cur), out + "+" + cur, res);
                helper(next, target, -stoll(cur), curNum - stoll(cur), out + "-" + cur, res);
                helper(next, target, diff * stoll(cur), (curNum - diff) + diff * stoll(cur), out + "*" + cur, res);
            } else {
                helper(next, target, stoll(cur), stoll(cur), cur, res);
            }
        }
    }
};

class Solution:
    def addOperators(self, num: str, target: int) -> List[str]:
        ans = []

        def dfs(start, prev_val, prev_sum, path):
            if start == len(num) and prev_sum == target:
                ans.append(path)
                return
            # besides above if check, if start>len(num), it will not go inside for loop
            for i in range(start, len(num)):
                if i != start and num[start] == '0':
                    break
                curr_val = int(num[start: i + 1])
                if start == 0: # or, judege by 'path' string is empty or not
                    dfs(i + 1, curr_val, curr_val, path + str(curr_val))
                else:
                    dfs(i + 1, curr_val, prev_sum + curr_val, path + "+" + str(curr_val))
                    dfs(i + 1, -curr_val, prev_sum - curr_val, path + "-" + str(curr_val))
                    dfs(
                        i + 1,
                        prev_val * curr_val, # i.e. diff
                        prev_sum - prev_val + prev_val * curr_val,
                        path + "*" + str(curr_val),
                    )

        dfs(0, 0, 0, "")
        return ans

############

class Solution(object):
  def addOperators(self, num, target):
    res, self.target = [], target
    for i in range(1, len(num) + 1):
      if i == 1 or (i > 1 and num[0] != "0"):  # prevent "00*" as a number
        self.dfs(num[i:], num[:i], int(num[:i]), int(num[:i]), res)  # this step put first number in the string
    return res

  def dfs(self, num, temp, cur, last, res):
    if not num:
      if cur == self.target:
        res.append(temp)
      return
    for i in range(1, len(num) + 1):
      val = num[:i]
      if i == 1 or (i > 1 and num[0] != "0"):  # prevent "00*" as a number
        self.dfs(num[i:], temp + "+" + val, cur + int(val), int(val), res)
        self.dfs(num[i:], temp + "-" + val, cur - int(val), -int(val), res)
        self.dfs(num[i:], temp + "*" + val, cur - last + last * int(val), last * int(val), res)

using System;
using System.Collections.Generic;

public class Expression
{
    public long Value;

    public override string ToString()
    {
        return Value.ToString();
    }
}

public class BinaryExpression : Expression
{
    public char Operator;

    public Expression LeftChild;
    public Expression RightChild;

    public override string ToString()
    {
        return string.Format("{0}{1}{2}", LeftChild, Operator, RightChild);
    }
}

public class Solution {
    public IList<string> AddOperators(string num, int target) {
        var results = new List<string>();
        if (string.IsNullOrEmpty(num)) return results;
        this.num = num;
        this.results = new List<Expression>[num.Length, num.Length, 3];
        foreach (var ex in Search(0, num.Length - 1, 0))
        {
            if (ex.Value == target)
            {
                results.Add(ex.ToString());
            }
        }
        return results;
    }

    private string num;
    private List<Expression>[,,] results;

    private List<Expression> Search(int left, int right, int level)
    {
        if (results[left, right, level] != null)
        {
            return results[left, right, level];
        }
        var result = new List<Expression>();
        if (level < 2)
        {
            for (var i = left + 1; i <= right; ++i)
            {
                List<Expression> leftResult, rightResult;
                leftResult = Search(left, i - 1, level);
                rightResult = Search(i, right, level + 1);
                foreach (var l in leftResult)
                {
                    foreach (var r in rightResult)
                    {
                        var newObjects = new List<Tuple<char, long>>();
                        if (level == 0)
                        {
                            newObjects.Add(Tuple.Create('+', l.Value + r.Value));
                            newObjects.Add(Tuple.Create('-', l.Value - r.Value));
                        }
                        else
                        {
                            newObjects.Add(Tuple.Create('*', l.Value * r.Value));
                        }
                        foreach (var newObject in newObjects)
                        {
                            result.Add(new BinaryExpression
                            {
                                Value = newObject.Item2,
                                Operator = newObject.Item1,
                                LeftChild = l,
                                RightChild = r
                            });
                        }
                    }
                }
            }
        }
        else
        {
            if (left == right || num[left] != '0')
            {
                long x = 0;
                for (var i = left; i <= right; ++i)
                {
                    x = x * 10 + num[i] - '0';
                }
                result.Add(new Expression
                {
                    Value = x
                });
            }
        }
        if (level < 2)
        {
            result.AddRange(Search(left, right, level + 1));
        }
        return results[left, right, level] = result;
    }
}

282 - Expression Add Operators

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions