Q:

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(answer(10000000))

A:

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.

