Questions tagged [subset-sum]
The subset-sum tag has no usage guidance.
2
votes
3answers
101 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
39 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
41 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
38 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\...
1
vote
0answers
55 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 S1 of set S so that ...
1
vote
1answer
31 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
31 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 ...
0
votes
0answers
38 views
Relation relationship between two given problems and Subset Sum
$$\begin{align*}
L&=\Big\{(a_1,...,a_{2n},k) : k,a_i \in \mathbb N ,\exists S \subset (a_1,...,a_{2n}) \text{ s.t. } |S|=n \text{ and } \sum_{a_i\in S} a_i =k\Big\}\\
L'&=\Big\{ (a_1,...,a_{...
1
vote
1answer
43 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
58 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
152 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
374 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 ...
0
votes
2answers
70 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
17 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
50 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
78 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
528 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
58 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
82 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
35 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
58 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
325 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
221 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
227 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
86 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
108 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
177 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
117 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
231 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
68 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
185 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 ...
