All Questions
19 questions
-1
votes
1
answer
78
views
Can someone spot the bug in this program? [closed]
Here is the problem https://www.geeksforgeeks.org/subset-sum-problem-dp-25/
I can't figure out where the code is going wrong
arr = [2, 7, 3, 8]
k = 5
n = 4
# initialisation
dp = [[0]*(k+1)]*(n+1)
...
- 3
0
votes
1
answer
102
views
Number of subsets with a given sum . Recursion not tracing few branches of the tree
I have written this code in python and it is not yielding the right answer for the input wt[]=[2,3,5,6,8,10] in this order . It is giving right answer for few other combinations like wt[]=[3,2,6,10,8,...
0
votes
1
answer
1k
views
Subset sum variation, dynamic programming
I'm trying to do the classic subset sum problem with the caveat that the sum of the subset should get as close as possible to tgt without exceeding it. Here is my recurrence which finds how far away ...
- 19
0
votes
2
answers
3k
views
Getting all subsets from subset sum problem on Python using Dynamic Programming
I am trying to extract all subsets from a list of elements which add up to a certain value.
Example -
List = [1,3,4,5,6]
Sum - 9
Output Expected = [[3,6],[5,4]]
Have tried different approaches and ...
- 45
1
vote
0
answers
511
views
subset sum included negative numbers with dynamic approach
The problem is negative numbers are breaking the classical dynamic approach solution of subset sum. I wrote an algorithm that can deal with non-negative array content but I need an algorithm for ...
- 1,186
1
vote
3
answers
2k
views
Print all subsets of an array with sum equal to the target sum
Given an array of N elements find all the subsets of array with sum equal to the target value.
I have seen all the old questions available on this site related to subset sum but none of them worked ...
- 71
0
votes
0
answers
190
views
How do I return a subset with a sum closest to the integer 's' when the array does not add up to 's' in Python?
I'm writing a function that takes an integer s and an array of positive integers A and returns an array consisting of elements of A which add up to s.
If there is no subset that adds up to s, the ...
- 1
2
votes
1
answer
772
views
Recovering Subsets in Subset Sum Problem - Not All Subsets Appear
Brushing up on dynamic programming (DP) when I came across this problem. I managed to use DP to determine how many solutions there are in the subset sum problem.
def SetSum(num_set, num_sum):
#...
- 43
1
vote
1
answer
142
views
Is there a way to print 2 equally sum sub list, of a list?
So i have this code here which works and returns True, if there is 2 sub lists with the same sum (1/2 of the total sum)
read more about Partition Equal Subset Sum
Example:
s = Solution()
print(s....
- 521
0
votes
1
answer
801
views
Find only one subset sum with a specified value
Not printing all subsets with a specified sum, but only one and with the smallest time complexity.
found = False
def subset_sum(numbers, target, partial=[]):
global found
s = sum(partial)
...
- 68
0
votes
0
answers
176
views
Parity Subset Sum Dynamic Programming Python Solution
Was given this question as an assignment:
Consider the following variant of the subset sum problem. You are given positive integers
(a1, . . . , an), along with a target value t. You are to design an ...
1
vote
0
answers
51
views
Splitting element in an array such that the new array has 2 subset solution to the subset sum to zero problem
I have a problem that is not quite the same as a subset sum problem and is best shown with an example.
Given the N item array of real numbers which is guaranteed to sum up to zero,
Example: [13.6, ...
- 703
0
votes
0
answers
95
views
subset sum divisible in two groups with equal elements
Problem: Given an array of size N, is it possible to divide the array into two groups of exactly N/2 elements each such that the sum of elements in both the groups are equal?
What I tried: use the ...
- 976
0
votes
1
answer
870
views
Subset Sum Dynamic Programming
def subset(array, target):
sol = [[False for x in range(target + 1)] for x in range(len(array) + 1)]
for i in range(len(array)+1):
sol[i][0] = True
for i in range(1,(len(array)+1)):...
- 23
0
votes
1
answer
112
views
Why does my Dynamic Programming Approach to the SSP always work?
Why does my code succeed 100% of the time? I want to generate 100 random samples of this code's output to measure the speed, but each time I run I receive 100 true outcomes and 0 false outcomes. Can ...
- 27