Questions tagged [subset-sum]
The subset-sum tag has no usage guidance.
47
questions
-1
votes
0answers
21 views
smallest subset with given sum
How to find the smallest subset with a given sum?
All elements are integers.
I have an array of integers and I want to find a given sum with the least number of
element possible
with both the ...
-1
votes
0answers
13 views
How to select M max Sum from N stack
We are given N stacks of variable length. We need to choose M element such that sum is maximum.
example
3 3
stack a)
1 2 200
stack b)
5 10 7
stack c)
4 6
the answer will be 1+2+200 = 203 .
1
vote
1answer
27 views
Recover boolean vector from dot products
Question:
I want to determine a boolean vector $b \in \{0,1\}^n$ consisting of zeros and ones, but cannot access it directly. I can only call a black-box computer code which will take the dot product ...
0
votes
0answers
23 views
Finding fixed size submatrix with highest sum
I have a matrix, which has N rows and M columns. I need to find n rows and m columns, which has the highest sum. Matrix consists of positive numbers. Not optimal solutions are ok. For example N=M=4; n=...
0
votes
1answer
40 views
Prove Subset-Sum is NP-complete - Alternative reduction?
It is well known the Subset-Sum problem is NP-complete. This can be shown using a reduction from the 3SAT problem. I am wondering: is there any other NP-Complete problem that could be reduced to the ...
0
votes
1answer
45 views
Time complexity of subset sum problem with reals instead?
It is well known that the conventional subset sum problem with integers is NP-complete. What if the array elements can be any real numbers and also target sum can be any real number? Is it NP-complete ...
0
votes
1answer
57 views
Find all subsets with a given sum
How to choose from a set of positive numbers all the subsets that sum to some number x?
For example if the set $S=[1,1,2,3,4,5,6,7]$ and I'm searching for all the subsets that sum to $7$ I would have $...
1
vote
1answer
49 views
Finding the Range of Solutions for KSum Variation
Preface
I asked a question before where I was looking to understand the complexity class of the following problem:
Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such ...
2
votes
1answer
44 views
Counting the number of subsets with positive sum
I have some constant vector $\mathbf{s}$ on $n$ dimensions, where every element of $\mathbf{s}$ is a real number, and I would like to multiply it by every possible $n$-dimensional binary vector $\...
0
votes
1answer
52 views
Job scheduling approximation
In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf
Lemma 5 is given as:
The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
0
votes
1answer
501 views
Partition array into k subsets
We are given an array and a number K. Partition array into K subsets such that
let MaxSum be the maximum sum of among subsets.
We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$
Is ...
0
votes
1answer
39 views
invariant of bin packing
We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We ...
1
vote
0answers
22 views
Given a subset of numbers $1, \dots, n$, find the minimal subset of numbers $1, \dots, n$ sums of every subset of which cover all sums of first subset
Given a subset $A = \{a_1, a_2, \dots, a_k\}$ of numbers $\{1, 2, \dots, n\}$, find another subset $B = \{b_1, b_2, \dots, b_t\}$ of numbers $\{1, 2, \dots, n\}$ of minimal size (that is, minimise $t$)...
1
vote
1answer
42 views
Does a polynomial solution to weakly-NP Complete problem mean P = NP?
Suppose someone finds a polynomial solution to weakly-NP Complete problem does that mean P = NP.
4
votes
0answers
112 views
Subset Sum Search Problem for Input with At Most One Solution [closed]
Edit: This question has been reasked on TCS.
We first consider the search version of the subset sum problem: Given a set $S$ of $n$ naturals, find a subset of $S$ that sums to exactly $W$. My ...
2
votes
2answers
99 views
Check if K-Sum Variation is NP-Complete
Problem
Given a range of integers $\{a,a+1,...,b-1,b\}$, find a subset of size $k$ such that the sum is equal to $s$.
Question
This problem came from evaluating some scheduling algorithms that I am ...
0
votes
0answers
13 views
Intuitively, my problem is a mix of perfect hashing, tree spanning, combinatorial stuff - Ordered Decision Tree?
The problem I'm trying to solve is difficult to to give a single name, but I'll call it the ordered decision tree problem.
Imagine a row of commands:
...
2
votes
3answers
217 views
N subsets with a given sum?
How to efficiently ¹⁾ choose from a set of numbers $S$, a given number $n$ of disjoint subsets, each with a given sum $K$ of chosen elements?
¹⁾ Not as in $P$, I just want something smarter than $O(n^...
1
vote
0answers
43 views
Find a partition of multiset of binomial coefficients with constriants
Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $
0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of ...
1
vote
1answer
99 views
Reducing subset sum to even subset sum
I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even ...
1
vote
0answers
45 views
Subset sum problem with an extra condition [closed]
A sub-set sum problem is described that giving a set of integers $S$ and a constant $C$, find a subset $s$ of $S$ so that the sum of integers in $s$ is maximum but not greater than $C$.
$$maximize\...
2
votes
1answer
276 views
Proof of NP Completeness of set-partition problem
I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help.
MY METHOD
In subset sum problem we have to find a subset $S_1$ of set $S$ so ...
1
vote
1answer
43 views
Subset sum problem, given that a valid subset exists
I have a problem at work. I need to find a subset of a set of positive integers that sums to a certain value. I know there is a subset but I need to find it. Is this new problem the same as the ...
1
vote
1answer
67 views
Subset sum exponential solution - how does the sorting work?
The wiki for the subset sum problem found here it states that you take the list of N elements and split it into two lists of N/2 elements. You then generate all the subsets for each list (each having ...
1
vote
1answer
46 views
How to find sets of polynomially bounded numbers whose subset sums are different?
Let $n$ be any positibe integer and set $N=\{1,\dots,n\}$. Now select two arbitrary but different subsets of $N$, say $S$ and $S'$. We are interested in finding a function $\pi(A)=\sum_{i\in A}a_i$ ...
1
vote
1answer
70 views
Is this an $NP$-complete problem: Product-2-Partition
I want to prove the NP-hardness of my problem P in scheduling. I was trying with Partition, 3-Partition and Subset product, But neither was successful.
Now, I can reduce a problem, say PRODUCT-2-...
2
votes
1answer
221 views
Maximum Equal Sum K Subsequences
Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum.
Example:
...
2
votes
2answers
2k views
Find the lexicographically smallest order of N numbers such that the total of N numbers <= Threshold value
GIven a number N, Threshold T and an array A. Find the lexicographically smallest order of N numbers from A such that the total of these N numbers is <= T.
This question is a simplification of ...
1
vote
2answers
752 views
Understanding algorithm for maximum sum of non-consecutive elements
There is a well-known problem in CS of finding the maximum sum of non-consecutive integers in a list. There is even an SO post about how to solve it:
https://stackoverflow.com/questions/4487438/...
1
vote
1answer
18 views
Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k
Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40)
How would I find the maximum possible size of S, where S is a ...
2
votes
1answer
51 views
Can the subset sum problem work with an undefined set?
To give a brief outline of my actual problem, I'm attempting to identify possible impurities in proteins. I have a theoretical mass and an experimental mass, and the difference between the two would ...
2
votes
1answer
131 views
Subset sum into a consecutive range vs. standard subset sum
The following problems live in integer domain.
I want to find a subset of $\{x_0, x_1, \ldots, x_{n-1}\}$ such that the subset's elements sum to any number in a prescribed interval $[X,X+k]$, $k\geq ...
1
vote
0answers
857 views
k-way set partition problem--dynamic programming solution
I was reading up on the set partition problem on this site of Wikipedia: https://en.m.wikipedia.org/wiki/Partition_problem
Among other things, they present a DP approach to solving the equal subset ...
0
votes
2answers
87 views
Determine if an array is divisible in pairs of equal sum
I'm currently studying the time complexity of the solution provided by my teacher to this problem, and I can't understand the logic:
Let A be an unordered array of positive natural numbers. Write ...
2
votes
0answers
125 views
Modified Subset Sum Problem
Given an array of $n$ integers $A$, and some value $m$, determine if it is possible, by using certain amounts of each element, to get a total sum equal to $m$. Consider that you can use any amount of ...
1
vote
1answer
37 views
Algorithm for this problem on generating all permutations
I am trying to come up with an efficient algorithm to solve the following problem but not able to design anything nice. I am encountering this problem for a project I am pursuing. Following is an ...
3
votes
1answer
69 views
What is the complexity class of this variant of Subset sum?
Let's represent Subset Sum problem with binary arrays instead of numbers.
Example: given two-dimensional array
[1, 0, 0] (4)
[1, 0, 1] (5)
[0, 0, 1] (1)
is there ...
1
vote
2answers
438 views
Is subset sum problem with multiplicities NP-complete?
To be specific, the problem is formalized as follows.
Given a set of integers $\{a_1,\ldots,a_n\}$, determine whether there exist non-negative integers $x_1,\ldots,x_n$ such that $a_1x_1+\cdots+...
3
votes
1answer
286 views
Is integer factorization reducible to subset sum?
Is it possible to solve the FACT (integer factorization) problem in polynomial time if we know the polynomial Subset Sum algorithm?
We assume that we know the algorithm solving the problem of Subset ...
0
votes
1answer
325 views
How to show that some problem is in NP and that it's NP-complete
I need some help with the following question:
Recall the subset sum problem, which is known to be NP-complete:
"Given a finite set of natural numbers and a number $n$, decide whether a subset ...
0
votes
0answers
99 views
there exists a O(n) algorithm for subset sum under certain conditions?
I was wondering if anybody knows if there is an algorithm for Subset-sum, preferably exact, having a $O(n)$ Time Complexity or near-linear ($n$ = number of elements in the input set)
I remember that ...
4
votes
1answer
114 views
Subset Sum for {1,…,n}
In general, the subset sum problem is NP-Complete. However, what if we say that our set is $\{1,...,n\}$? Is there a formula/combinatorial calculation that says how many subsets of $\{1,...,n\}$ have ...
0
votes
0answers
236 views
'meet in the middle' combined with Dynamic Programming for subset sum
What is the reason why nobody has combined the 'meet in the middle' approach with the Dynamic Programming for subset sum?
I found it curious that is a kind of a open problem.. as a matter of fact I ...
-1
votes
1answer
192 views
Find biggest K, such that any subset of size less than K is not affecting the array
Let's say we have given array $A = \{a_1, a_2, a_3,\dots,a_n\}$ of size $n$, and integer $L$, we want to find biggest integer $K$, such that the array without any subset of size $x, x\leq K$ will have ...
1
vote
1answer
254 views
Solving Subset Sum Without the Use of Dynamic Programming
I am looking for algorithmic techniques to solve the Subset Sum Problem in pseudopolynomial time. There is, of course, a textbook dynamic programming approach for Subset Sum. Have any other ...
1
vote
1answer
87 views
Does the subset sum problem remain $NP$ complete when we increase word size and restrict number of words?
Is the problem
'Given $m=\big\lceil{n^b}\big\rceil$ with $b\in(0,1)$ integers $a_1,\cdots,a_m$ each with $\lceil\log_2 |a_i|\rceil=\big\lceil n^a\big\rceil$ with $a\in[1,\infty)$ is there a subset ...
1
vote
4answers
224 views
What are some concrete (near-)“worst-case” examples of subset-sum?
I've written a subset-sum solver. It outputs all subsets that sum to a given value, iteratively.
I'm measuring its performance by the average amount of time taken per subset found.
However, I suspect ...
