Interesting variation to the subset sum problem

Question

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?

Answer 1

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

Answer 2

Note before reading:

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.

---

Original answer

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

Answer 3

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

Faster pseudo-polynomial time algorithms for PARTITION

Answer 4

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;
with Ada.Text_IO; use Ada.Text_IO;

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