# Questions tagged [subset-sum]

Questions about the NP-complete problem Subset Sum.

70 questions
Filter by
Sorted by
Tagged with
17 views

### Unconstrained subset sum vs constrained subset sum?

In class, we discussed two question types: constrained subset-sum and unconstrained subset-sum. Let me define the question specifically and then I will mention what I am confused by. Question 1: ...
31 views

### Is is possible to create a SUBSET-SUM instance that each subset is “unique”?

Given a SUBSET-SUM instance $S$ with a weight $W$, is it possible to create, in polynomial time, a new non-empty instance $T$ (at most the same length as $S$) with weight $M$, that for each non-empty ...
45 views

### How can you modify a SUBSET-SUM instance so evaluating a set outputs either 0 or 1?

An SUBSET-SUM instance is a list of $n$ integers $\{ a_1, a_2,... a_n\}$. To evaluate a subset is to output the sum of a subset. However, I want to know, is it possible to create a new instance $T$, ...
26 views

### Are inputs of NP problems too implicit?

I'm reading on wikipedia about P vs NP and I have a question. Consider the zero sum problem: given a set of integer A, determine if there is a non empty subset such that the sum of all its elements is ...
16 views

71 views

### Enumerate all valid orders of subset sums

Given an positive integer $n$, we define an order of subset sums (or simply, an order, when there is no ambiguity) to be a sequence of all subsets of $\{1,\ldots,n\}$. For example, when $n=2$, the ...
126 views

### Two versions of Subset Sum Problem

I keep seeing two versions of the Subset Sum Problem. The first and seemingly least common is: Given an integer bound $W$ and a collection of $n$ items, each with a positive integer weight $w_i$, ...
338 views

### Subset sum problem for permutations

Given permutations $g_1,\,\ldots, g_m \in S_n$ of size $n$ and target permutation $g \in S_n$, decide if there exists a subset of $\{g_1,\, \ldots, g_m\}$, which composition in some order (or, ...
37 views

70 views

### Divide a number in k powers of 2

Example N = 9 and K=3 4 + 4 + 1 = 9 . What I have tried. We can not go on dividing with 2. We can use unbounded knapsack with array elements from 2^0 to 2^32.
108 views

### multiset variant of subset sum problem known algorithms

I have been working in the time analysis for an exact solver I designed for the subset sum problem accepting multisets as input instances, and determined its time complexity to be dependent on the ...
116 views

97 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 ...
88 views

63 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 ...
162 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 ...
1k 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 ...
62 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 ...
192 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 ...
47 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$ ...
### Is this an $NP$-complete problem: Product-2-Partition
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: ...