7 votes
Accepted

Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value

You are on the right track. It turns out the original question can be solved by a greedy algorithm. (A full blown solution by dynamic programming as I tried a while ago is both an overkill on coding ...
John L.'s user avatar
  • 39k
6 votes

Is integer factorization reducible to subset sum?

Yes, such a reduction exists. Subset Sum is NP-complete. FACT is in NP. Therefore, by the definition of NP-complete, there exists a reduction from FACT to Subset Sum. To find such a reduction ...
D.W.'s user avatar
  • 159k
6 votes
Accepted

Find the smallest subarray with sum larger than a threshold

You can solve your problem in linear time using a "sliding window" algorithm. Let $i,j$ be two pointers initialized to $1$, and denote by $\sigma(i,j)$ the sum $a_i + a_{i+1} + \dots + a_{j}$...
Steven's user avatar
  • 29.5k
4 votes
Accepted

Is subset sum problem with multiplicities NP-complete?

The problem can be solved in polynomial time. If any of the $a_i$ are zero, then the answer is "yes" (you can set the corresponding $x_i$ to 1, and all other $x_j$ to 0). So let's assume all of the $...
D.W.'s user avatar
  • 159k
4 votes
Accepted

Subset Sum With Interval Target

With positive integers only Consider the largest element $a_m$ in the input. We have the following cases: $a_m \in [\lceil\frac{1}{2}T\rceil, \lfloor\frac{3}{4}T\rfloor]$. We can simply choose $\{a_m\...
j_random_hacker's user avatar
3 votes

Does a polynomial solution to weakly-NP Complete problem mean P = NP?

All weakly NP-complete problems are NP-complete by definition, so yes, a polynomial time algorithm would imply P = NP.
Aditya Anand's user avatar
3 votes
Accepted

How to find sets of polynomially bounded numbers whose subset sums are different?

There are many functions that satisfy your condition. Here are a few. $a_i=1+c^{-i}$, for some constant $c\ge 2$. $a_i= 1+b_i/p_i$, where $p_i$ is the $i^{th}$ prime number and $b_i$ is any integer ...
John L.'s user avatar
  • 39k
3 votes
Accepted

What is the complexity class of this variant of Subset sum?

This is NP-hard. The associated decision problem is NP-complete. There are various ways to prove that. For instance, there's a straightforward reduction from exact cover; let the target array be all-...
D.W.'s user avatar
  • 159k
3 votes

Maximum Equal Sum K Subsequences

This problem is NP-complete by reduction to the given subset sum problem, which asks if there is a subset $S$ from a set with a certain sum $n$. Suppose we are given such an instance and that your ...
orlp's user avatar
  • 13.4k
3 votes
Accepted

Partition array into k subsets

I'm assuming by $sum(i)$ you mean that given an ordering of the $k$ partitioned subsets, sum over all elements of the $i$th subset. The $k=2$ case is the optimization variant of the set partitioning ...
BearAqua in Agua's user avatar
3 votes

Counting the number of subsets with positive sum

Suppose that you could solve this in $T(n)$. Given a list of positive integers $a_1,\ldots,a_n$ and a target $T$, consider the two instances $a_1,\ldots,a_n,-T$ and $a_1,\ldots,a_n,-T+1$. Denoting by $...
Yuval Filmus's user avatar
3 votes

Divide a number in k powers of 2

If $k>N$, this cannot be done (as $\forall p_1,\dots, p_k\geq 0,\sum_{i=1}^k 2^{p_i}\geq k>N$) If $k\leq N$: Write $N$ in binary, and denote by $n$ the number of $1$s. We have written $N$ as a ...
integrator's user avatar
  • 1,110
3 votes
Accepted

complexity of a variant of the subset sum problem

It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the ...
Steven's user avatar
  • 29.5k
3 votes
Accepted

Solve SUBSET SUM for Reciprocals of Primes

The observation is that the denominator of the reduced fraction $1/p_{i_1} + \cdots + 1/p_{i_m}$ is $p_{i_1} \cdots p_{i_m}$. To see this, it suffices to notice that the (unreduced) numerator isn't ...
Yuval Filmus's user avatar
3 votes
Accepted

Two versions of Subset Sum Problem

Given an instance of the second problem, we can easily reduce it to an instance of the (decision version of) the first problem: simply take $W = k$. There is a subset of sum at least $k$ and at most $...
Yuval Filmus's user avatar
3 votes
Accepted

How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

However, I want to know, is it possible to create a new instance T, the same size as the original set S, that any subset in S that evaluates to W, the corresponding subset in T (the numbers taken from ...
Tom van der Zanden's user avatar
3 votes
Accepted

Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum

This is not what amortized analysis means: you can not infer the worst case runtime of an algorithm by plotting the actual execution time on larger and larger instances of some specific structure. ...
Juho's user avatar
  • 22.6k
3 votes

Minimum absolute value of subset sums of integer values

We give a Turing reduction from the $\mathrm{SubsetSum}$ problem. Suppose we are given a $\mathrm{SubsetSum}$ instance $(A, k)$ where w.l.o.g. $A$ only contains positive integers, i.e. we want to find ...
Watercrystal's user avatar
  • 1,526
3 votes
Accepted

Algorithm for computing the sum of symmetric sums (better than $\mathcal{O}(2^N)$ )

But $g(x,a)$ is linear in $a$ so if you can compute it efficiently for two different values of $a$ then you can compute it efficiently for all $a$?
prim's user avatar
  • 46
3 votes

Subset Sum With Interval Target

With negative integers permitted Unlike the SSITP problem restricted to positive integers, when negative integers are permitted the problem is NP-complete. I'll show this by reduction from ordinary ...
j_random_hacker's user avatar
3 votes

Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

For a set $S = \{s_1,\dotsc,s_n\}$. Construct a polynomial $P(x): x^{s_1} + x^{s_2} + \dotsc + x^{s_n}$. Multiply the polynomial by itself three times, i.e., $P(x) \cdot P(x) \cdot P(x)$. Let this ...
Inuyasha Yagami's user avatar
3 votes
Accepted

Complexity of a variant of Subset Sum problem

The problem is polynomial-time solvable using a reduction to 0-1 knapsack problem. Take a knapsack of size $W = n+1$. Take $n$ items of size $a_i$ and value $a_i$. The maximum value obtained is $n+1$ ...
Inuyasha Yagami's user avatar
3 votes

Is this set covering problem NP-Hard?

This problem is NP-Hard. Consider a decision problem of this problem: Whether there exists a partition of S, such that |U'| + |U''| = 2|U|? This problem is equal to the problem of 2-DSC, which has ...
zqq's user avatar
  • 69
3 votes
Accepted

Linear-time constant-space 1/2-approximation algorithm for the maximum subset sum problem

The idea is to set $K/2$ as the target. If there is any given number that is at least $K/2$, just return it. Otherwise, all given numbers are $<K/2$. If the sum of all given numbers is $\le K$, ...
John L.'s user avatar
  • 39k
3 votes
Accepted

Subset ${\tt XOR}$ problem

The problem is in $P$. It can be solved in polynomial time with Gaussian elimination. Build a $n\times n$ boolean matrix $M$, whose $i$th row is the $i$th bit-string in $X$. All arithmetic will be ...
D.W.'s user avatar
  • 159k
2 votes

Is subset sum problem with multiplicities NP-complete?

This problem lies in P. To see this, formulate this problem it as an integer linear program (ILP): For $x\in \mathbb{Z}^n$, maximize $\sum_{i=1}^n x_i$ under the constraint $\sum_{i=1}^n a_ix_i = 0$...
Discrete lizard's user avatar
  • 8,248
2 votes
Accepted

Subset sum into a consecutive range vs. standard subset sum

This answer assumes that a Yes instance of your problem with elements $x_0,\ldots,x_{n-1}$ and targets $[X,X+1]$ is one in which there is a subset summing to either $X$ or $X+1$. Given an instance of ...
Yuval Filmus's user avatar
2 votes

Subset sum exponential solution - how does the sorting work?

The idea is that two sorted lists of length $n$ can be merged into one sorted list of length $2n$ in time $O(n)$. This is a standard procedure used in the mergesort algorithm. Given a list of integers ...
Yuval Filmus's user avatar
2 votes

What are some concrete (near-)"worst-case" examples of subset-sum?

It's not clear how to formally define worst-case (or near-worst-case) instances, but here is something you could try. The idea is to combine the following two tidbits: We know some hard instances ...
Yuval Filmus's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible