# Interesting variation to the subset sum problem

An interesting variation of the subset sum problem was presented to me by a friend from work:

Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) that contains exactly a elements, whose sum is equal to K?

He claims that this can be done with time complexity O(nKa), I was unable to come up with a dynamic programming algorithm that achieved this running time. Can it be done?

• I guess here $k = K$, perhaps you could fix this? – Jukka Suomela Nov 2 '10 at 11:45
• Thanks, good catch. I wonder if that caused all the confusion =/. – ntsue Nov 2 '10 at 11:49
• Can't you do this using dynamic programming? Let $A[i,j,m]$ be 1 iff the there is a subset of the first $i$ elements in the set of size $j$ which sums up to $m$. You are asking for $A[n,a,k]$. – Kaveh Nov 2 '10 at 11:49
• Cross-posted on StackOverflow. – M.S. Dousti Nov 2 '10 at 12:25
• I had a related question. Can we expend the dynamic programming approach to count the number of solutions? – h.a Aug 7 '12 at 23:29

Doesn't the usual (pseudo-polynomial time) dynamic programming algorithm solve this, with a minor tweak?

The usual approach is to have a table with flags "there is a subset of $x_1,x_2,...,x_i$ with sum $s$" for all $i = 1, 2, ..., n$ and $s = 0, 1, ..., K$.

The minor modification is to have a table with flags "there is a subset of $x_1,x_2,...,x_i$ with $c$ elements and sum $s$" for all $i = 1, 2, ..., n$, $c = 1, 2, ..., a$, and $s = 0, 1, ..., K$.

• Thanks! This was also just answered for me on another forum. – ntsue Nov 2 '10 at 11:45

In my answer, I assumed that $K$ is a constant. However, as pointed out by Jukka and the OP, this is not always the case. Here I clarify why it is so, and then continue with the original answer. I did not delete my original answer as per Policy on deleting incorrect answers.

### About $K$

We are given as input a set $S=\\{s_1,s_2,\ldots,s_n\\}$ of integers. The size of the input is $|S| = \sum_{i=1}^{n}{|s_i|}$, and we have $0 < K \le \sum_{i=1}^{n}{s_i}$. Therefore, $K$ can be large enough to be exponential in the size of the input.

I don't think this is possible. Assume, towards contradiction, that there exist an algorithm (I call it algorithm X) which solves the subset-some variation you mentioned in time $O(nka)$. Then, I show an algorithm for the original subset sum, whose time complexity is $O(n^3k)$.

In the original subset sum problem, the subset R (of the set S) can contain $1, 2, \ldots, n$ elements. So, let $a = 1, 2, \ldots, n$, and test each $a$ using algorithm X. The time complexity of such procedure will be: $\sum\limits_{a=1}^{n}{O(nka)} = O(n^3k)$. This contradicts the assumption that the subset sum problem requires superpolynomial time (unless $\rm{P}=\rm{NP}$, which is unlikely.)

• Please note that $K$ here is exponential in the size of input. – Jukka Suomela Nov 2 '10 at 11:37
• @Jukka, yes I believe that right – ntsue Nov 2 '10 at 11:39
• I chose to delete my incorrect answer. No point having two duplicate incorrect answers. – Dave Clarke Nov 2 '10 at 12:23

There is an $\tilde{O}(nK)$ time algorithm given by Chao Xu:

Faster pseudo-polynomial time algorithms for PARTITION

I searched the net for a program to solve an instance of this particular variation of the subset sum problem. I did not find any program, but this page with hints. So I used it and attempted to implement it as described above. The following is what I had hoped to find when I searched. It solved the problem I had. For the next one searching (who could be me in 20 years); this is what worked for me:

with Ada.Command_Line; use Ada.Command_Line;

--  Solves the subset sum problem for a given subset size. If the stack
--  overflows, allow more memory usage (ulimit -s <large value>) or solve a
--  smaller problem. Usage : subset_sum <subset_size> <subset_sum> <value> ...
procedure Subset_Sum is
type Tag_Type is new Positive range 1 .. 2**16-1;
for Tag_Type'Size use 16;

type Value_Value_Type is new Positive range 1 .. 2**16 - 1;
for Value_Value_Type'Size use 16;
type Value_Type is record
Value : Value_Value_Type;
Tag : Tag_Type;
end record;
Set : array (1 .. Argument_Count - 2) of Value_Type;

Subset_Size : constant Positive := Positive'Value (Argument (1));
Subset_Sum : constant Positive := Positive'Value (Argument (2));

type Flag_Value_Type is new Natural range 0 .. 2**16 - 1;
for Flag_Value_Type'Size use 16;
type Flag_Type is record
Value : Flag_Value_Type;
Tag : Tag_Type;
end record;
T : array (1 .. Subset_Size, 1 .. Set'Length, 1 .. Subset_Sum) of Flag_Type
:= (others => (others => (others => (0, Tag_Type'Last))));

procedure Print_Solutions
(SuSize, Last, SuSum : in Natural; Result : in String);
procedure Print_Solutions
(SuSize, Last, SuSum : in Natural; Result : in String)
is
begin
if 0 = SuSize and 0 = SuSum then
Put_Line (Result);
else
for I in reverse 1 .. Last loop
declare
Flag : constant Flag_Type := T (SuSize, I, SuSum);
begin
if 0 < Flag.Value then
if 1 = I or else Flag /= T (SuSize, I - 1, SuSum) then
Print_Solutions
(SuSize - 1,
I - 1,
SuSum - Natural (Flag.Value),
(Flag.Value'Img) &

--  Uncomment the line below to append the sequence
--  number to each value.
--  Integer (-Flag.Tag)'Img &

Result);
end if;
end if;
end;
end loop;
end if;
end Print_Solutions;

Input_Error : exception;

begin

--  Tag the input values with a sequence number.
begin
Set (1) := (Value_Value_Type'Value (Argument (3)), 1);
for I in 2 .. Set'Last loop
Set (I) := (Value_Value_Type'Value (Argument (I + 2)), Tag_Type (I));
end loop;
exception
when Constraint_Error => raise Input_Error;
end;

--  Flag all cells that should be flagged for subset size 1.
for I in Set'Range loop
if Positive (Set (I).Value) <= Subset_Sum then
for J in I .. Set'Length loop
T (1, J, Positive (Set (I).Value)) :=
(Flag_Value_Type (Set (I).Value), Set (I).Tag);
end loop;
end if;
end loop;

--  Flag all cells that should be flagged for subset size > 1.
for I in 2 .. Subset_Size loop
for J in 2 .. Set'Length loop
for K in 2 .. Subset_Sum loop
T (I, J, K) := T (I, J - 1, K);
end loop;
for K in Positive (Set (J).Value) + 1 .. Subset_Sum loop
if 0 < T (I - 1, J - 1, K - Positive (Set (J).Value)).Value then
T (I, J, K) := (Flag_Value_Type (Set (J).Value), Set (J).Tag);
end if;
end loop;
end loop;
end loop;

Print_Solutions (Subset_Size, Set'Length, Subset_Sum, "");

exception
when Input_Error =>
Put_Line
(Standard_Error,
"Wrong argument (try ""subset_sum <subset_size> <subset_sum> <value> "
& "<value> ..."")");
Set_Exit_Status (Failure);
end Subset_Sum;


Use case: Suppose that an organization had a meeting with a voting. The published information says that 5 shareholders with 4387 votes voted Yes. The electoral register lists participants with the votes 1, 4, 800, 19, 37, 505, 1002, 991, 1288, 455, 387, 367, 367, 199, 425, 1581 and 2054. The program solves this:

\$ ./subset_sum 5 4387 1 4 800 19 37 505 1002 991 1288 455 387 367 367 199 425 1581 2054
800 37 505 991 2054


The program is designed to handle duplicate values by attaching a sequence number to each, making it unique. The sequence numbers can be included in the printed solutions. In the above use case, the sequence number can be useful as a reference back into the electoral register.

• Please replace your 100+ lines of Ada with pseudocode, explain what it does and how it works. Blocks of code are not appropriate in answers, here because implementing in a real programming language tends to introduce large amounts of fiddly detail that obscures the underlying algorithm. – David Richerby Dec 13 '14 at 11:05