<h3>Note before reading:</h3>

<p>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 <a href="https://cstheory.meta.stackexchange.com/q/386/873">Policy on deleting incorrect answers</a>.</p>

<h3>About $K$</h3>

<p>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 &lt; K \le \sum_{i=1}^{n}{s_i}$. Therefore, $K$ can be large enough to be <strong>exponential</strong> in the size of the input.</p>

<hr>

<h3>Original answer</h3>

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

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

CC BY-SA 2.5
2010-11-02T11:37:12.250Z
Please note that $K$ here is exponential in the size of input.
Jukka Suomela
CC BY-SA 2.5
2010-11-02T11:39:16.063Z
@Jukka, yes I believe that right
ntsue
CC BY-SA 2.5
2010-11-02T12:23:37.763Z
I chose to delete my incorrect answer. No point having two duplicate incorrect answers.
Dave Clarke
CC BY-SA 2.5
2010-11-02T11:02:00.463Z
2010-11-02T12:15:11.337Z
2017-03-16T15:45:13.547Z
Sadeq Dousti
<p>There is an $\tilde{O}(nK)$ time algorithm given by Chao Xu:</p>

<p><a href="https://cstheory.stackexchange.com/questions/4644/faster-pseudo-polynomial-time-algorithms-for-partition">Faster pseudo-polynomial time algorithms for PARTITION</a></p>

CC BY-SA 4.0
2018-09-12T22:14:10.253Z
2018-09-12T22:14:10.253Z
hqztrue
<p>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 <strong>as described above</strong>. 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:</p>

<pre><code>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 &lt;large value&gt;) or solve a
--  smaller problem. Usage : subset_sum &lt;subset_size&gt; &lt;subset_sum&gt; &lt;value&gt; ...
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 =&gt; (others =&gt; (others =&gt; (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 &lt; 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) &amp;

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

                        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 =&gt; 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) &lt;= 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 &gt; 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 &lt; 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 =&gt;
      Put_Line
        (Standard_Error,
         "Wrong argument (try ""subset_sum &lt;subset_size&gt; &lt;subset_sum&gt; &lt;value&gt; "
         &amp; "&lt;value&gt; ..."")");
      Set_Exit_Status (Failure);
end Subset_Sum;
</code></pre>

<p><strong>Use case:</strong> 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:</p>

<pre><code>$ ./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
</code></pre>

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

CC BY-SA 3.0
2014-12-13T11:05:05.440Z
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
CC BY-SA 3.0
2014-12-12T12:16:31.600Z
2014-12-14T18:46:02.190Z
2014-12-14T18:46:02.190Z
odalman
<p>Doesn't the usual (pseudo-polynomial time) dynamic programming algorithm solve this, with a minor tweak?</p>

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

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

CC BY-SA 2.5
2010-11-02T11:45:42.220Z
Thanks! This was also just answered for me on another forum.
ntsue
CC BY-SA 2.5
2010-11-02T11:43:05.240Z
2010-11-02T11:43:05.240Z
Jukka Suomela
<p>An interesting variation of the subset sum problem was presented to me by a friend from work:</p>

<p>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 <strong>exactly a elements</strong>, whose sum is equal to K?</p>

<p>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?</p>

CC BY-SA 3.0
2012-08-07T23:29:09.263Z
I had a related question. Can we expend the dynamic programming approach to count the number of solutions?
h.a
CC BY-SA 2.5
2010-11-02T11:45:12.007Z
I guess here $k = K$, perhaps you could fix this?
Jukka Suomela
CC BY-SA 2.5
2010-11-02T11:49:11.483Z
Thanks, good catch. I wonder if that caused all the confusion =/.
ntsue
CC BY-SA 2.5
2010-11-02T11:49:17.350Z
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
CC BY-SA 2.5
2010-11-02T12:25:51.763Z
Cross-posted on [StackOverflow](http://stackoverflow.com/q/4076711/459391).
Sadeq Dousti
<cc.complexity-theory><ds.algorithms><dynamic-algorithms>
Interesting variation to the subset sum problem
ntsue
# Interesting variation to the subset sum problem

(Asked by: username_0 on 2010-11-02)

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?

**Tags:** cc.complexity-theory, ds.algorithms, dynamic-algorithms

> **Comments:**
> **username_2**: I guess here $k = K$, perhaps you could fix this?  
> **username_0**: Thanks, good catch. I wonder if that caused all the confusion =/.  
> **username_3**: 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]$.  
> **username_4**: Cross-posted on [StackOverflow](http://stackoverflow.com/q/4076711/459391).  
> **username_1**: I had a related question. Can we expend the dynamic programming approach to count the number of solutions?  

---

## 4 answers

### Answer by username_2 on 2010-11-02. Score: 11 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks! This was also just answered for me on another forum.  

---

### Answer by username_4 on 2010-11-02. Score: 3

### 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](https://cstheory.meta.stackexchange.com/q/386/873).

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

> **Comments:**
> **username_2**: Please note that $K$ here is exponential in the size of input.  
> **username_0**: @Jukka, yes I believe that right  
> **username_5**: I chose to delete my incorrect answer. No point having two duplicate incorrect answers.  

---

### Answer by username_6 on 2018-09-12. Score: 1

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

[Faster pseudo-polynomial time algorithms for PARTITION](https://cstheory.stackexchange.com/questions/4644/faster-pseudo-polynomial-time-algorithms-for-partition)


---

### Answer by username_7 on 2014-12-12. Score: -2

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 ) or solve a
--  smaller problem. Usage : subset_sum    ...
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    "
         & " ..."")");
      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.

> **Comments:**
> **username_8**: 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.  

---

