Meta 数字串目标表达式：拼接、加减与开头负号

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 只允许+和−，没有乘法；每个数字按顺序使用一次，不能插入括号。多位数字禁止前导零，单独0允许。
• 一个变体允许开头−，另一个只在数字之间插符号；通过allow_leading_minus显式选择。示例不单独输出−0以避免等价冗余。
• 返回所有表达式文本，输出顺序示例排序；原始字符串必须非空ASCII数字。
• 追加同题仅+/*变体：可拼接整数，无减号/首负号，普通乘法优先于加法；用target_expressions_plus_times，不能调用只+/-接口冒充。

解题路线

1. 状态(start,total,expression)枚举下一个数字块的终点。首块作为正值，也可按变体加负首块；之后对每块扩展+与−，走到末尾且total==target才收集。
2. 拼接是在选择块边界时完成，不应先当单个数字求和再把运算符删掉；12−3的12是数值十二。用逐位累积构造数值，遇首0后不再扩更长块。
3. 此实现用显式栈避免递归层数上限，但状态量仍指数级；不能把“不递归”说成解决大数据爆炸。无乘法无需lastTerm修正，若扩展*必须保留当前乘法项处理优先级。
4. target超大可以安全判断已完成表达式，但中途简单按total>target剪枝不成立，后续减法可降回目标。安全上界需计算剩余数字可形成的最大绝对贡献。
5. 仅加乘生成时状态增加lastTerm。追加*number把总值从total改为total−lastTerm+lastTerm×number，维护完整最后乘法项；追加+则lastTerm=number。仍枚举切分并禁止多位前导零。

手动走一遍

123、target6得到1+2+3；target9得到12−3。105目标6可用1+0+5，不可用带05的表达式。允许负首块时12目标1可用−1+2。 仅+/*输入123 target7可得1+2*3；左到右无优先级会误算9。输入105 target5可得1*0+5、10*5不是5，不能把05当整数chunk。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def target_expressions(digits, target, allow_leading_minus=False):
    """Insert +, -, or concatenate; no multiply; disallow multi-digit leading zeros."""
    if not digits or any(c not in '0123456789' for c in digits):
        raise ValueError("nonempty ASCII decimal digits required")
    results = []
    stack = [(0, 0, '')]
    while stack:
        start, total, expression = stack.pop()
        if start == len(digits):
            if total == target:
                results.append(expression)
            continue
        number = 0
        for end in range(start, len(digits)):
            if end > start and digits[start] == '0':
                break
            number = number * 10 + ord(digits[end]) - ord('0')
            chunk = digits[start:end + 1]
            if start == 0:
                stack.append((end + 1, number, chunk))
                if allow_leading_minus and number != 0:
                    stack.append((end + 1, -number, '-' + chunk))
            else:
                stack.append((end + 1, total + number, expression + '+' + chunk))
                stack.append((end + 1, total - number, expression + '-' + chunk))
    return sorted(results)


def target_expressions_plus_times(digits,target):
    """Insert +, * or concatenate; ordinary precedence, no unary sign/leading zero."""
    if not digits or any(ch not in '0123456789' for ch in digits):raise ValueError('ASCII digits')
    result=[];stack=[(0,0,0,'')]
    while stack:
        start,total,last,expression=stack.pop()
        if start==len(digits):
            if total==target:result.append(expression)
            continue
        number=0
        for end in range(start,len(digits)):
            if end>start and digits[start]=='0':break
            number=number*10+ord(digits[end])-ord('0');chunk=digits[start:end+1]
            if start==0:stack.append((end+1,number,number,chunk))
            else:
                stack.append((end+1,total+number,number,expression+'+'+chunk))
                product=last*number
                stack.append((end+1,total-last+product,product,expression+'*'+chunk))
    return sorted(result)

复杂度

n−1个间隙三选一带来至多3^(n−1)表达式，首负号至多倍增；字符串构建和排序有额外输出成本。辅助栈保留待探索分支，最坏与搜索状态规模相关，不宣称O(n)严格空间。

易错点与追问

容易失分的边界

• 标准带乘法的表达式算法不能原样用来解释“只有加减”变体；规则决定状态。
• 跳过0这个块会漏掉合法表达式；禁止的是多位前导零。

继续深挖

• 若只问存在性，可对(start,total)做memo，但total取值多仍可能爆炸，返回所有答案不能用全局visited直接删同值不同表达式。
• 若输入允许前导零整块，移除该剪枝即可，但输出是否将01保留文本要明确。