Python function to add or subtract digits of a number

My problem is that I'm trying to write a function PlusMinus(num) which will read the integer being passed, and determine if it's possible to separate the digits of the integer with either a plus or minus sign to form an expression which evaluates to zero.

For example: if num is 35132 then it's possible to separate the digits the following way, 3 - 5 + 1 + 3 - 2, and this expression equals 0.

The function should return a string of the signs used, so for this example the program should return "-++-". If it's not possible to get the digit expression to equal zero, it should return the string "not possible". If there are multiple ways to get the final expression to equal zero, it should return the one that contains more minus characters. For example: if num is 26712 the function should return "-+--" and not "+-+-".

Sample Test Cases:

Input: 199
Output: not possible 

Input: 26712 
Output: -+--

My code:

num=int(input())
PlusMinus(num)
def PlusMinus(num):
    s=str(num)
    l=len(s)
    rs=''
    r=0
    if(l<2):
        print("not possible")
    else:
        for i in range(1,l):
            if i<2:
                r=int(s[0])-int(s[1])
                rs='-'
            else:
                if r<=0:
                    r=int(r)+int(s[i])
                    rs+='+'
                else:
                    r=int(r)-int(s[i])
                    rs+='-'
        if(r==0):
            print(rs)
        else:
            print("not possible")

This is a fun problem. Your code works for the test cases you've outlined in your post, but the logic falls down in some cases. For example, your code naively attempts to add a subtract sign if the current sum is greater than 0, and a plus sign if not. This means that if we try:

945
--

We get the correct answer, however if we try:

459
not possible

We get an incorrect answer, as clearly 4 + 5 - 9 = 0, so we expect to get +-.

My approach to the problem would be to use itertools.product to generate all possible combinations of plus and minus signs, starting with ---... and ending with +++..., and loop through them in order, breaking if we find a solution. This brute force solution is also naive, as with some analysis & heuristics, we could eliminate a fair few solutions, but it does work and will provide the correct answer.

Code:

import itertools

def PlusMinus(num):
    # make our num into a string
    s=str(num)
    
    # For each possible operations combination:
    for op in itertools.product('-+', repeat=len(s)-1):
        # If when applied, we make 0
        if apply_ops(s, op) == 0:
            # Return the operations as a string
            return ''.join(op)
    # If we've exhausted all possibilities, it's not possible
    return 'not possible'
    
# Apply a series of operations op to a string s
def apply_ops(s, op):
    # Set return val to the first digit of s
    rv = int(s[0])
    
    # For each remaining digit, either increment or decrement according to the
    # operation
    for i, n in enumerate(s[1:]):
        if op[i] == '+':
            rv += int(n)
        else:
            rv -= int(n)
    # Return result
    return rv
    
num=int(input())
print(PlusMinus(num))

Tests:

945
--
459
+-
26712
-+--
199
not possible