# Questions tagged [subset-sum]

Questions about the NP-complete problem Subset Sum.

120 questions
Filter by
Sorted by
Tagged with
41 views

• 161
54 views

### Why does this approach not work on the SubSet Sum Problem?

I was reading this post, and in it I learned how to make difficult instances of the SubSet Sum Problem. There the guy who responded to the post says that it is necessary to have density 1.0 and all ...
• 1
1 vote
69 views

### Subset ${\tt XOR}$ problem

Motivation. This is a variant of the subset sum problem involving the bitwise ${\tt XOR}$ operation. Problem. Given a set $X$ of $n$ bit-strings of length $n$, determine if there is a non-empty subset ...
1 vote
464 views

### Find the smallest subarray with sum larger than a threshold

Given a set of $n$ positive numbers $\{a_1,\ldots,a_n\}$ and a positive target $T$, find a subset $S$ from $\{a_1,\ldots,a_n\}$ of contiguous elements, that is $S=\{a_i,a_{i+1},a_{i+2},\ldots\}$ for ...
• 109
51 views

### HAMILTONIAN PATH AND SUBSETSUM

If we were to discover a deterministic algorithm capable of deciding, in polynomial time, whether a given graph contains a Hamiltonian path, would that imply that the problem SUBSETSUM belongs to P? ...
• 1
82 views

### Subset sum problem with big items

Consider the variant of the Subset Sum problem, where the input is a list of $2 m + 1$ positive integers of sum $2 S$, and the goal is to find a subset with the largest sum that is at most $S$. The ...
• 6,070
1 vote
61 views

### Is this variant of multiset covering problem NP-hard?

Consider this variant of multiset covering problem. Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ and $s_k \neq \emptyset$ for all $k$...
• 11
1 vote
65 views

### Understanding David Pisinger's balanced algorithm for the subset-sum problem with bounded weights

I'm trying to understand David Pisinger's balanced algorithm for the subset-sum problem with bounded weights, which can be found on page 5 of his paper Linear Time Algorithms for Knapsack Problems ...
75 views

### Efficient algorithm for finding the target sum

Task. Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers ...
41 views

### List of weakly NP-HARD problems

I need a list of at least 10 weakly NP-HARD problems. I already know the Knapsack problem, partition problem and subset sum problem. Please introduce other weakly NP-hard problems to me.
23 views

• 35
1 vote
649 views

### Finding equal-sum subsets from two arrays

Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 <= A[i] <= M$ and $1 <= B[i] <= N$ for all $i$ (...
101 views

47 views

### I'm looking for an algorithm to find all subsets of a set S with subset sums between a given min and max

Given a set S of numbers, min and max. Find all sebsets of numbers from S with a subset sum larger or equal to min and smaller or equal to max. The following article says that there's an algorithm ...
1 vote
40 views

• 261
1 vote
92 views

### Is there a pseudopolynomial time algorithm for this subset sum variant?

The subset sum problem is: given a list of $n$ positive integers, and a positive number $T$, find a sub-list with largest sum that is at most $T$. The problem can be found in time polynomial in $n$ ...
• 6,070
1 vote
103 views

### Given a set, generate all permutations whose sums are less or equal to a given number

I am looking for a way to generate every permutation (so order does matter) of a set of positive numbers whose sum is less than (or equal to) a given limit. I need to find the permutations themselves, ...
• 121
465 views

• 23
406 views

### Python closest subset sum function

I'm writing a closestSubset(s,A) function that takes an integer s and an array of positive integers A and returns an array consisting of elements of A which add up to s. If there is no subset that ...
• 1
106 views

### Is this set covering problem NP-Hard?

Consider this variant of set covering problem. Input: a collection of sets $S = \{s_1, s_2, \ldots, s_n\}$ and a universal set $U$, in which $s_k \subseteq U$ for all $k$. The problem is, divide $S$ ...
• 69
140 views

### Is there a name for this modification to the subset sum problem?

Let $S = \{\{x_{1},y_{1},z_{1}\},\{x_{2},y_{2},z_{2}\}, \ldots, \{x_{n},y_{n},z_{n}\}\}$ and a target $t$. Let $S_i$ be the subset list $\{x_{i},y_{i},z_{i}\}$. Find a subset sum that sums to $t$ such ...
• 49
117 views

### Subset sum with only two item types

Suppose we have $r$ copies of the integer $a$ and $t$ copies of the integer $b$, and a capacity $C$. We would like to find the maximum sum of the given integers, that is at most $C$. This is a special ...
• 6,070
103 views

### Subset Sum With Interval Integer Target

Define the subset sum with interval integer target problem (SSIITP) as follows: SSIITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$. An integer $T$. SSIITP Output: True, if ...
1 vote
156 views

### Convert float array to lower or higher integer, find sum(integers) == round(sum(floats)), reducible to subset sum?

You have an array of floats, for example: ...
1 vote
49 views

### In terms of P=?NP, would a P time solution to Subset-Sum have to work in P time when there is no subset that sums to T in the input?

This question is asking for clarification on what P=?NP is asking specifically. I've read the official problem description: here and it seems like P=?NP is primarily concerned with inputs that result ...
342 views

### Complexity of a variant of Subset Sum problem

This is the variant of SSP: Given $n$ positive integer points $a_1, \ldots, a_n$ which are all at most $n$, does there exist a subset $\{a_i\}_{i \in P}$, such that its summation is exactly $n+1$? My ...
777 views

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

Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for ...
• 21
497 views

### Subset Sum With Interval Target

Define the subset sum with interval target problem (SSITP) as follows: SSITP Input: A multiset $S = \{a_1, …, a_p\}$ of positive integers $a_i$ such that $\sum_{a_i \in S} a_i = T$. SSITP Output: ...
1 vote
158 views

### Does an FPTAS exist for the multiple subset sum problem when m is fixed and c is not a variable?

From Wikipedia Multiple subset sum: The multiple subset sum problem (MSSP) is a generalization of the subset sum problem (SSP): given a multiset $S$ of $n$ integers, and an integer $m$, the goal is to ...
1 vote
829 views

### SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
• 113
195 views

### Is there an FPTAS for 3-way number partitioning?

The maximization problem of the 3-way number partitioning reads as follows: given $n$ positive integers, partition them into 3 subsets such that the smallest sum is as large as possible. It is known ...
44 views

### Prove SubsetSum is polyequivalent to SubsetSum with surplus

I'm solving problem 13.17 of What can be computed?, which is asking to prove $\text{SubsetSum} \equiv_{P} \text{SubsetSumWithFives}$. Here is the definition of SubsetSumWithFives. SUBSETSUMWITHFIVES: ...
1 vote
72 views

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

Let denote $\mathbf{x} = \{x_1,x_2,...,x_N \}$ with $x_i \in \Bbb R$ for $i=1,...,N$ and $f(\mathbf{x},n)$ be the $n$-th symmetric sum of the set $\mathbf{x}$  f(\mathbf{x},n) = \sum_{\sigma_1,...,\...
• 113
246 views

### The subset sum problem is not in P because the question is about lossy compressed data? Why not?

Where is there a gap or error in my reasoning? The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1). The compression ...
• 33
1 vote
569 views

### Reduction from SUBSET-SUM to 0-1-INT-PROG

The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$. I am trying to prove that 0-1-INT-PROG ...
• 258