On the Largest Cardinality Subset Sum

2012 ACM Subject Classification Theory of computation $\to$ Design and analysis of algorithms

Funding Anubhav Dhar: Supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) grant number 559177164.

Pranjal Dutta: Supported by Nanyang Assistant Professorship as well as by the SUG Grant (#025774-00001), funded by Nanyang Technological University Singapore.

Mahesh Sreekumar Rajasree: Funded by the European Union (ERC, LACONIC, 101041207). Views and opinions expressed are those of the authors only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.

Karol Węgrzycki: Supported by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) grant number 559177164.

Introduction

The Subset Sum problem asks whether, given nonnegative integers $a_1,\ldots,a_n$ and a target $t$, there exists a subset of the input items that sums exactly to $t$. It is a basic example of an NP-complete problem that admits a pseudopolynomial algorithm: Bellman’s dynamic program takes $O(nt)$ time [3]. Subsequent work has substantially improved the dependence on $n$ and $t$. Koiliaris and Xu gave a deterministic $\widetilde{O}(\sqrt{nt})$-time algorithm [15], and Bringmann [4] and, later, Jin and Wu [14] gave randomized $\widetilde{O}(n+t)$-time algorithms. Recently, Chan derandomized these results and gave a deterministic $\widetilde{O}(t)$-time algorithm for Subset sum [6]. These algorithms determine which sums in $\{0,\ldots,t\}$ are attainable, i.e. appear as a sum of some subset of input items. A natural next question is what can be learned about the subsets attaining a given target. We study the maximum size of such a subset. Items are distinguished by their indices, even when their values are equal.

Thus LCSS refines the usual decision problem: it distinguishes two attainable representations of the same target by their cardinalities. It also has a direct interpretation as a structured 0-1 knapsack problem: we give item $i$ weight $a_i$ and profit $Ma_i+1$, where $M>n$, and set the knapsack capacity to $t$. Every subset of weight exactly $t$ has profit $Mt+|S|$, whereas every subset of weight at most $t-1$ has profit at most $M(t-1)+n<Mt$. Consequently, if $t$ is attainable, an optimal knapsack solution is a subset that sums to $t$ and has maximum cardinality among all the subsets that sum to $t$; if it is unattainable, the optimal profit is below $Mt$. This embedding explains why recording only attainable sums, as in ordinary subset sum, does not immediately give the desired optimum. In fact, at the fine-grained level, this places LCSS in between the subset sum and the knapsack problem; LCSS is at least as hard as subset sum, and knapsack is at least as hard as LCSS. These observations make LCSS an interesting problem to study.

0-1 knapsack for single capacity: Jin [12] gave a deterministic algorithm that runs in time $\widetilde{O}(n+a_{\max}^2)$, whereas Bringman [5] also (independently) gave a deterministic $\widetilde{O}(n+a_{\max}^2)$-time algorithm for the bounded knapsack problem (where each item comes with a multiplicity). Here $a_{\max}$ denotes the maximum weight item. Using the above reduction and these two algorithms, we get $\widetilde{O}(n+a_{\max}^2)$-time algorithm for LCSS.

There is also a useful analogy with change-making. The change-making problem minimizes the number of coins summing to a target, with unlimited use of each denomination. In LCSS, each input item can be used at most once, and the number of selected items is maximized. Both problems invite a distinction between a single specified target and all targets up to a bound. This distinction has proved consequential for change-making: Chan and He obtained near-linear-in-$t$ algorithms for the single-target problem and an $\widetilde{O}(t^{4/3})$-time algorithm for its all-targets version [7]. We likewise study both versions of LCSS.

A straightforward dynamic program computes the optimum for every sum up to $t$ in $O(nt)$ time: when item $a_i$ is processed, the best cardinality at sum $s$ is compared with one plus the previous best cardinality at $s-a_i$. Koiliaris and Xu [15] also discuss the problem of subset sums with cardinality information. They further provide an $\widetilde{O}(nt)$-time algorithm that gives all the attainable subset sums with complete cardinality information, not just the maximum. However, their improvement of the complexity from $\widetilde{O}(nt)$ to $\widetilde{O}(\sqrt{nt})$ loses information regarding cardinalities. This suggests that solving LCSS in $\widetilde{O}(\sqrt{nt})$ time is an interesting problem. On the other hand, Axiotis and Tzamos [2] give an $O(Dt)$-time algorithm for the knapsack problem, with all weights being less than or equal to $t$, where $D$ denotes the number of distinct items in the instance. This algorithm, with the aforementioned reduction of LCSS to knapsack, gives a $O(Dt)$-time algorithm for AT-LCSS, and consequently for LCSS too.

The subset-sum algorithms in [4, 14, 6] do not, on their own, preserve the largest cardinality for each sum. Related work has examined other forms of cardinality information: Dutta and Rajasree [9] study the Hamming weights of all solutions when the number of solutions is bounded, while Antonopoulos, Pagourtzis, Petsalakis, and Vasilakis [1] discuss algorithms for subset-sum variants with target-cardinality constraints.

Projection Subset Sum and related work

AT-LCSS has a direct application to Projection Subset Sum, introduced by Dutta and Rajasree [10]. Given a nonnegative integer vector $Z=(a_1,\ldots,a_n)$ and a nonnegative integer target $t$, the search problem asks for an integer vector $X=(x_1,\ldots,x_n)$ and a subset $S\subseteq[n]$ satisfying $\sum_{i\in S}x_i=t$ that minimize $\lVert Z-X\rVert_p$. For $t>0$, the set $S$ is necessarily nonempty. Their near-linear randomized algorithm for the $\ell_1$ case assumes that every attainable sum has a unique representation; they also give an $O(nt)$ algorithm under that assumption [10].

For a fixed nonempty subset $S$, the amount by which its original sum misses $t$ is $d=t-\Sigma(S)$. In the $\ell_\infty$ case, if integer-valued coordinates may be changed without sign restrictions, the smallest possible maximum coordinate change is $\lceil|d|/|S|\rceil$. More selected items allow the discrepancy to be spread over more coordinates. For general $p\ge1$, the corresponding exact integer cost further depends on $\Sigma(S)$ and $|S|$; see § 6. Among nonempty subsets with the same sum, a largest subset minimizes the projection cost. Therefore, an AT-LCSS solution supplies exactly the cardinality information needed to compare the best projection costs for different attainable sums, including sums above $t$.

A related motivation for Projection Subset Sum comes from neural-network pruning. The strong lottery ticket hypothesis asks whether a randomly initialized network contains a subnetwork that approximates a given target network [20, 18]. Pensia et al. [19] study this question using random subset sums, while Xiong, Liao, and Kyrillidis [22] additionally allow bounded perturbations of the weights. This combines selecting existing weights with slightly modifying them to improve approximation. Projection Subset Sum captures a related question for a list of numbers: how little must the numbers be changed so that some subset sums exactly to a prescribed target?

Our results

The previous discussion already gives us $\widetilde{O}(n+d_{\max}^2)$-time and $O(n+Dt)$-time algorithms for LCSS. Our main result is a faster pseudopolynomial-time algorithm for the regime when $a_{\max}=\widetilde{\Theta}(n^{1/4}\sqrt{t})$ and $D=\widetilde{O}(\sqrt{n})$. Note that $\widetilde{O}(\cdot)$ hides polylogarithmic factors.

Thus, up to polylogarithmic factors, our algorithm reduces the coefficient of $t$ from $n$ to $\sqrt{n}$ in the running time complexity. It computes the exact maximum cardinality of a subset summing to $t$, or reports that $t$ is unattainable, with high probability.

Very recently, Jin and Mao [13, Proposition D.3] give a conditional result for LCSS on positive inputs. If there is an algorithm running in $T(n,\Delta)$ that decomposes all subset sums of $n$ positive integers bounded by $\Delta$ into an arithmetic progression with a common [difference], then they managed to show that LCSS can be solved in $\widetilde{O}(n+\sqrt{n}\cdot t+T(n,3t\sqrt{n}))$ time. Their result would match the running time of our result, if $T(n,\Delta)\le\widetilde{O}(n+\Delta)$, however the existance of such a fast algorithm is open [13]. Theorem 3 avoids this unresolved assumption and achieves the same running-time bound unconditionally.

Our second result focuses on the all-targets version, in which the maximum cardinality must be computed for every target $s\in\{1,\ldots,t\}$.

This algorithm improves the discussed $O(n+Dt)$ algorithm when $D=\widetilde{\omega}(t^{1/2})$. The probability guarantee holds simultaneously for all targets. Beyond the time needed to read the input, the running time depends only on $t$, rather than on the number of items. The two bounds are complementary. Since the all-targets algorithm also solves any single-target instance, together they yield an $\widetilde{O}(n+t\min\{\sqrt{n},\sqrt{t}\})$-time algorithm for LCSS.

By exploiting the cardinality information provided by AT-LCSS, we also give a randomized $\widetilde{O}(n+t^{3/2})$-time algorithm for Projection Subset Sum in the $\ell_p$ norm (PSS$_p$) for all fixed $p\ge1$.

And, for the $\ell_1$ norm, we give a randomized $\widetilde{O}(n+t)$-time algorithm using Bringmann’s subset-sum algorithm; see Theorem 27. Both the PSS algorithms output an optimal vector $X$ and a set $S$ witnessing its feasibility, with failure probability at most $1/3$, without the unique-representation assumption.

Organization of the paper. § 2 gives an overview of our algorithms. § 3 introduces the notation and tools used. § 4 presents the algorithm for LCSS via solving TCSS. The algorithm for AT-LCSS can be found in § 5. The algorithms for Projection Subset Sum can be found in § 6. Appendix § 7 contains deferred lemmas and proofs.

Declaration on the Use of AI Tools. Generative AI tools, including ChatGPT and Claude, were used solely for proofreading, language editing, improving presentation, and identifying potential inconsistencies. All technical contributions are original to the authors, who independently verified relevant AI-generated suggestions and take full responsibility for the manuscript.

Technical Overview

Previously, Bringmann [4] gave an $\widetilde{O}(n+t)$-time algorithm to output all possible subset sums capped by an integer $t$, in an application of $n$ elements. This was later simplified by Jin and Wu [14], and then derandomized by Chan [6]. For this paper, we give a bivariate equivalent result of [14], which computes both cardinalities and sums of all possible subsets with caps in both cardinality and the sum.

A proof idea is as follows: Consider Bringmann’s algorithm [4]. Essentially, the algorithm consists of a collection of convolutions to keep track of sums. Whenever a sum exceeds $t$, this sum is dropped from further consideration. One can modify Bringmann’s algorithm to simply consider pairs of cardinalities and sums, then convolve these sets of pairs, and drop pairs which exceed either the cardinality bound or the sum cap. The resulting algorithm has the required running time. Similarly, Jin and Wu’s algorithm [14] can also be modified accordingly to prove Lemma 6; for completeness, we provide a complete proof in Appendix A.2.

Solving Largest Cardinality Subset Sum

We start by focusing on the intermediate problem of finding whether a subset of a given sum and a given cardinality exists.