# Dynamic Program to solve an NP-complete partitioning problem

I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!

Let $$A = \{ a_1, a_2, ..., a_n \}$$ be a set where $$a_i \in \mathbb{N}$$ for $$i=1,...,n$$.

The goal is to determine whether there exist two disjoint subsets $$M,N \subset A$$ such that the sum of all elements in $$M$$ is equal to exactly $$\textit{twice}$$ the sum of all elements in $$N,$$ and $$M \not = \emptyset$$ and $$N \not = \emptyset.$$

• Let $t$ be the sum of all input values. I think your best bet will be an $O(nt^2)$-time, $O(t^2)$-space algorithm that generalises the usual Knapsack algorithm by looping through all items in some order, and generating all pairs of sums that can be formed from the first $i$ elements -- by adding the $i$-th item to either element of all pairs of sums $(a, b)$ that can be formed from the first $i-1$ items. At the end, look for pairs of the form $(a, 2a)$. This is only pseudopolynomial time, but I'm certain ordinary Knapsack can be reduced to this. – j_random_hacker Apr 9 at 0:58
• Ins't the answer trivially yes? Pick $M=N=\emptyset$. – Steven Apr 9 at 16:00
• That's my bad, both $M$ and $N$ must not be empty. Will add that in now. – yellowsuzuki Apr 9 at 16:13
• Thank you both for your answers! – yellowsuzuki Apr 9 at 21:22

Let $$\sigma(S)$$ denote the sum of all the elements in $$S$$ and $$A_i = \{a_1, \dots, a_i\}$$.

Given, $$i=0,\dots,n$$ and $$w \in \mathbb{Z}$$, define $$OPT[i,w]$$ as the mazimum cardinality of a subset $$S \cup S' \subseteq A_i$$ where $$S \cap S' = \emptyset$$ and $$\sigma(S) - 2\sigma(S') = w$$. If no possible choice for $$S$$ and $$S'$$ exists, then let $$OPT[i,w]=-\infty$$.

According to the above definition: $$OPT[0, w] = \begin{cases} 0 & \text{if } w=0 \\ -\infty & \text{if } w \neq 0 \\ \end{cases}$$

For $$i>0$$: $$OPT[i, w] = \max\{ OPT[i-1, w], 1 + OPT[i-1, w-a_i], 1+ OPT[i-1, w+2a_i] \}.$$

The answer to your problem is true iff $$OPT[n, 0] > 0$$. Each $$OPT[i, w]$$ can be computed in constant time (if you have already computed the values of $$OPT[i-1, \cdot]$$). Moreover, there are only $$O(n)$$ possible choices for $$i$$ and $$O(t)$$ sensible choices for $$w$$, where $$t = \sum_{i=1}^n a_i$$. This gives you a dynamic programming algorithm with time complexity $$O(n t)$$ and space complexity $$O(t)$$.

• That checks out!! Thanks a lot for the answer, appreciate it!! – yellowsuzuki Apr 9 at 21:22
• Nice answer! You could use a single bit for each $OPT[i,w]$, and set a global "solution exists" flag when some $OPT[i, 0]$ can be achieved from some $OPT[i-1, x]$ with $x \ne 0$. – j_random_hacker Apr 9 at 21:51
• @j_random_hacker, yep! My first write up used one bit per $OPT[i,w]$ but then I had the problem that $N=M=\emptyset$ would always be a solution. I thought of keeping two bits per $OPT[i,w]$ ("is there a solution?" and "is there a non-trivial solution?") but it felt "hacky" so I looked for a "natural" subproblem definition that would circumvent the problem altogether. – Steven Apr 9 at 22:04