# A special case of the SUBSET SUM problem

Consider the following special case of SUBSET SUM

Inputs: Positive integers $$a$$ and $$b$$ with $$a \ne b$$, and positive integers $$k$$ and $$t$$, with $$k$$ specified in unary.

Encoding: These inputs (compactly) encode a list $$L$$ of length $$2^k$$ where there are exactly $$\binom{k}{i}$$ terms of the form $$a^{k-i}b^{i}$$, for $$i=0, \dots, k$$.

Output: Is there a subset $$D$$ of $$L$$ whose sum is precisely $$t$$?

A certificate for this problem is a list $$(n_0, \dots, n_k)$$, where $$n_i$$ is the number of terms of the form $$a^{k-i}b^{i}$$ that exist in $$D$$. Assuming that $$k$$ is given in unary, such a certificate can be verified in polynomial time.

Any thoughts on whether this problem might be NP-Hard?

The setup is quite strange since even though the problem is closely related to subset sum, the inputs $$a,b,k$$ encode a list $$L$$ that is long, so it is not entirely clear how or if a connection exists.