Solving a variation of the "Partition Problem"

In my version of the Partition Problem, I have a set of weights that are all powers of three (1, 3, 9, 27 etc.). I only have one of each weight. There is some object (the weight of this object is input) on the left side of a scale and I need to add weights to either side to balance it. I can choose not to use a weight if I so choose (denoted by a '-').

Right now, my program converts the inputted weight into ternary and, if all the digits are 1's and 0's, just feeds in the appropriate factor of three into a list. Otherwise, it generates every possibility, iterating through them until both sides are equal. This is, predictably, very slow. I know the partition problem is NP-C but is there any optimizations I can make here?

```
import string
import pdb
import itertools

def nearestpowerof3(x):
numbers = '012'
if x < 0:
sign = -1
elif x == 0:
return numbers[0]
else:
sign = 1
x *= sign
digits = list()
while x:
digits.append(numbers[x % 3])
x = int(x / 3)
if sign < 0:
digits.append('-')
digits.reverse()
ternary = ''.join(digits)
exp = int(len(ternary))
return exp, 3 ** exp, ternary

def answer(x):
product = []

tern = str(nearestpowerof3(x)[2])
print(tern)
if tern.find('2') == -1:
print('HELLO')
for digit in tern[::-1]:
if digit == '1':
product.append("R")
elif digit == '0':
product.append("L")
return product
else:
for product in itertools.product('RL-', repeat=len(tern) + 1):
left = x
right = 0
for i in range(len(product)):
if product[i] == 'R':
right += 3**i
elif product[i] == 'L':
left += 3**i
if left == right:
if product[-1] == '-' and product[-2] != '-':
product = product[:-1]
return product
print

I don't see a partition problem here. What the task suggests is a representation of a given number in the form of \$\Sigma a_n3^n\$ where \$a_n \in \{-1,0,1\}\$. I highly recommend proving to (or at least convincing) yourself that every number has such representation. Then you may want to see how few first numbers are represented:

1                   1
    2                  -1  1
    3                   0  1
    4                   1  1
    5                  -1 -1  1
    6                   0 -1  1
    7                   1 -1  1
    8                  -1  0  1
    9                   0  0  1
    10                  1  0  1
    11                 -1  1  1
    12                  0  1  1
    13                  1  1  1
    14                 -1 -1 -1  1

(first column is for 1, second for 3, third for 9, etc) and figure out the rule of sequencing the coefficients for each power of 3 (think reminders). The actual coding becomes straightforward.

StackExchange Code Review Q#97836, answer score: 4