On the Largest Cardinality Subset Sum

We study Largest Cardinality Subset Sum (LCSS): given $n$ nonnegative integers and a target $t$, compute a subset summing to $t$ with maximum cardinality. We also consider its all-targets version (ATLCSS), which asks for this maximum for every sum $s\in \{1,\dots ,t\}$. The LCSS problem sits squarely between the subset sum and the knapsack problem. A straightforward dynamic-programming algorithm runs in time $O(nt)$ and solves ATLCSS, and using Jin and Bringmann (both in STOC 2024, independent work) $0$-$1$ knapsack results we achieve a $\tilde{O}(n+a_{\max }^{})$-time deterministic algorithm for LCSS. Our main result is a randomized $\tilde{O}(n+\sqrt{n}t)$-time algorithm for LCSS. Then, we complement this result with a randomized $\tilde{O}(n+t^{3\mathrm{/}2})$-time algorithm for ATLCSS. Together, our two algorithms give a $\tilde{O}(n+t\min \{\sqrt{n},\sqrt{t}\})$-time algorithm for LCSS. As an application of ATLCSS, we solve the search version of Projection Subset Sum, introduced by Dutta and Rajasree (SYNSAC 2023), in $\tilde{O}(n+t^{3\mathrm{/}2})$ time for every fixed ${\mathrm{\ell }}_p$ norm with $p\ge 1$. For ${\mathrm{\ell }}_1$, we obtain $\tilde{O}(n+t)$ time, removing the unique-representation assumption required by their algorithm. Both algorithms output an optimal modified vector and a witnessing subset.