Questions tagged [subset-sum]
The subset-sum tag has no usage guidance.
1
vote
0answers
21 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
37 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
84 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
37 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
10 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
119 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
40 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
64 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
40 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
117 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
36 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
42 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
45 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
60 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
170 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
561 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
178 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
87 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
634 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
68 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
92 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
36 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
59 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
353 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
235 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
249 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
90 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
112 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
204 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
130 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
237 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
72 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
195 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 ...
