Stack Overflow
Stack Overflow

Questions tagged [subset-sum]

In computer science, the subset sum problem is one of the important problems in complexity theory and cryptography.

In computer science, the subset sum problem is one of the important problems in complexity theory and cryptography.

424 questions
308
votes
32 answers

Finding all possible combinations of numbers to reach a given sum

How would you go about testing all possible combinations of additions from a given set N of numbers so they add up to a given final number? A brief example: Set of numbers to add: N = {1,5,22,15,0,...} Desired result: 12345
James P.
  • 19,313
  • 27
  • 97
  • 155
55
votes
12 answers

Subset Sum algorithm

I am working on this problem: The Subset Sum problem takes as input a set X = {x1, x2 ,…, xn} of n integers and another integer K. The problem is to check if there exists a subset X' of X whose elements sum to K and finds the subset if there's any.…
Ahmed Moheb
  • 764
  • 1
  • 10
  • 20
41
votes
6 answers

Find all combinations of a list of numbers with a given sum

I have a list of numbers, e.g. numbers = [1, 2, 3, 7, 7, 9, 10] As you can see, numbers may appear more than once in this list. I need to get all combinations of these numbers that have a given sum, e.g. 10. The items in the combinations may not…
Byte Commander
  • 6,506
  • 6
  • 44
  • 71
33
votes
5 answers

Smallest number that cannot be formed from sum of numbers from array

This problem was asked to me in Amazon interview - Given a array of positive integers, you have to find the smallest positive integer that can not be formed from the sum of numbers from array. Example: Array:[4 13 2 3 1] result= 11 { Since 11 was…
user3187810
  • 333
  • 1
  • 3
  • 6
30
votes
7 answers

Number of subarrays divisible by k

I had the following question in an interview and, in spite of the fact that I gave a working implementation, it wasn't efficient enough. A slice of array A is any pair of integers (P, Q) such that 0 ≤ P ≤ Q < N. A slice (P, Q) of array A is…
antoniobg
  • 568
  • 1
  • 6
  • 10
18
votes
6 answers

Fast solution to Subset sum

Consider this way of solving the Subset sum problem: def subset_summing_to_zero (activities): subsets = {0: []} for (activity, cost) in activities.iteritems(): old_subsets = subsets subsets = {} for (prev_sum, subset) in…
Ecir Hana
  • 10,864
  • 13
  • 67
  • 117
16
votes
5 answers

Find the minimum number of elements required so that their sum equals or exceeds S

I know this can be done by sorting the array and taking the larger numbers until the required condition is met. That would take at least nlog(n) sorting time. Is there any improvement over nlog(n). We can assume all numbers are positive.
Shamim Hafiz - MSFT
  • 21,454
  • 43
  • 116
  • 176
11
votes
4 answers

Algorithm to find subset within two sets of integers whose sums match

I'm looking for an algorithm which can take two sets of integers (both positive and negative) and find subsets within each that have the same sum. The problem is similar to the subset sum problem except that I'm looking for subsets on both…
theburningmonk
  • 15,701
  • 14
  • 61
  • 104
11
votes
8 answers

Is this variant of the subset sum problem easier to solve?

I have a problem related to the subset sum problem and am wondering if the differences make it easier, i.e. solvable in a reasonable amount of time. Given a value V, a set size L, and a sequence of numbers [1,N] S, how many size L subsets of S sum…
dsimcha
  • 67,514
  • 53
  • 213
  • 334
11
votes
6 answers

Count number of subsets with sum equal to k

Given an array we need to find out the count of number of subsets having sum exactly equal to a given integer k. Please suggest an optimal algorithm for this problem. Here the actual subsets are not needed just the count will do. The array consists…
Abhra Dasgupta
  • 525
  • 1
  • 3
  • 12
10
votes
5 answers

Find all combinations of a set of numbers that add up to a certain total

I've seen a few solutions to similar problems, but they all require iteration over the number of items to be added together. Here's my goal: from a list of numbers, find all of the combinations (without replacement) that add up to a certain total.…
Kira Tebbe
  • 576
  • 8
  • 23
10
votes
2 answers

Multiple subset sum calculation

I have 2 sets, set A contains set of random numbers and set B's elements are sum of set A's subsets. For example, A = [8, 9, 15, 15, 33, 36, 39, 45, 46, 60, 68, 73, 80, 92, 96] B = [183, 36, 231, 128, 137] I want to find which number is sum of…
kalivance
  • 117
  • 1
  • 6
10
votes
3 answers

maximum sum of a subset of size K with sum less than M

Given: array of integers value K,M Question: Find the maximum sum which we can obtain from all K element subsets of given array such that sum is less than value M? is there a non dynamic programming solution available to this problem? or if it is…
Shivendra
  • 1,542
  • 2
  • 22
  • 35
9
votes
2 answers

Fast solution to Subset sum algorithm by Pisinger

This is a follow-up to my previous question. I still find it very interesting problem and as there is one algorithm which deserves more attention I'm posting it here. From Wikipedia: For the case that each xi is positive and bounded by the same…
Ecir Hana
  • 10,864
  • 13
  • 67
  • 117
8
votes
1 answer

Does a combination of K integers exist, so that their sum is equal to a given number?

I've been breaking a sweat over this question I've been asked to answer (it's technically homework). I've considered a hashtable but I'm kind of stuck on the exact specifics of how I'd make this work Here's the question: Given k sets of integers…
Arnon
  • 2,237
  • 15
  • 23
1
2 3
…
28 29