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.$

  • 1
    $\begingroup$ 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. $\endgroup$ Apr 9, 2020 at 0:58
  • $\begingroup$ Ins't the answer trivially yes? Pick $M=N=\emptyset$. $\endgroup$
    – Steven
    Apr 9, 2020 at 16:00
  • $\begingroup$ That's my bad, both $M$ and $N$ must not be empty. Will add that in now. $\endgroup$ Apr 9, 2020 at 16:13
  • $\begingroup$ Thank you both for your answers! $\endgroup$ Apr 9, 2020 at 21:22

1 Answer 1


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)$.

  • $\begingroup$ That checks out!! Thanks a lot for the answer, appreciate it!! $\endgroup$ Apr 9, 2020 at 21:22
  • $\begingroup$ 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$. $\endgroup$ Apr 9, 2020 at 21:51
  • $\begingroup$ @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. $\endgroup$
    – Steven
    Apr 9, 2020 at 22:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.