Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [subset-sum]

The tag has no usage guidance.

0
votes
1answer
49 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
35 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
40 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
50 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
155 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
38 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
41 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
97 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
71 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
155 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
42 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
89 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
44 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
211 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
39 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
54 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
66 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
184 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
702 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
622 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
107 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
782 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
75 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
102 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
67 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
392 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
268 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
308 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
97 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
113 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
217 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
164 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
246 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
85 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
214 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 ...