429 questions
6
votes
3
answers
309
views
Subset sum problem with selection constraint in large R dataset
I have a tibble:
sample_tibble <- tibble(
group = c(1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 4, 4),
threshold = c(100, 100, 100, 100, 100, 80, 80, 80, 80, 80, 80, 150, 150, 150,...
- 527
4
votes
4
answers
176
views
Checking if a set of numbers can be added up to a given value
I have a table like this:
set.seed(123)
random_table <- data.frame(
Column1 = sample(1:10, 5, replace = TRUE),
Column2 = sample(1:10, 5, replace = TRUE),
Column3 = sample(1:10, 5, replace = ...
- 839
0
votes
0
answers
79
views
Scala: minimal subset sum
Given a list of N positive integers.
The task is to print the size of minimal subset whose sum is greater than or equal to selected number (S)
For example:
Given: 4 8 10 12
For variants of S (for ...
- 1,296
0
votes
0
answers
46
views
How to show all answer when use OR-tool solve Subset Sum Problem
I'm doing a report on NP algorithm and I'm in charge of the mathematical modeling part. I have to use OR-tool to solve SSP but it's just show one answer.
from ortools.linear_solver import pywraplp
...
-1
votes
1
answer
77
views
Combing Subsets into Larger Sets
Ok I am super stuck on this one. I need a function that does the following.
Takes in a list of list.
input = [['A'], ['A', 'B'], ['A', 'B', 'C'], ['A', 'B'], ['X', 'Y'], ['A', 'B', 'C'], ['X'], ['A'], ...
- 1
-1
votes
7
answers
403
views
Counting the Number of Combinations that Match a Certain Condition
Here is my problem:
There are 5 candies (1,2,3,4,5) - each candy has the same "value" associated with its number (i.e. candy_1 has value=1, candy_2 has value=2, etc.).
In the future, I ...
- 5,877
1
vote
1
answer
99
views
all possible distinct non decreasing sequences(combinations) of numbers to reach the given sum with quick performance
I need to count all possible combinations of numbers to reach the given sum.
They should be non decreasing(every next number should be greater or equal to previous one).
Here is JavaScript code with ...
- 870
0
votes
2
answers
147
views
Number of subsets with zero sum - interpretation of the result
The code below is about dynamic programming with the subset zero sum algorithm.
In other words, it informs how many subsets sum to zero when adding their elements.
However, if the set is [2, -2], the ...
- 13.3k
1
vote
0
answers
24
views
Largest possible subset challenge failing
I am doing the following challenge:
Commander Lambda's space station is HUGE. And huge space stations take a LOT of power. Huge space stations with doomsday devices take even more power. To help meet ...
- 177
0
votes
0
answers
55
views
Is it possible to transform a whole number array (positive and negative) and a sum of a subset to a natural number (positive only) array and sum
From my understanding, if I want to create a natural number (positive only) representation of a whole number (positive and negative) array, it is quite straight forward... take the absolute value of ...
0
votes
0
answers
58
views
What is the runtime of this subset sum algorithm?
I want to solve the decision subset sum problem, so finding if a given set of integers has a subset that adds up to some T.
In the algorithm ordered arrays are sequentially searched through using the ...
4
votes
2
answers
408
views
Algorithm to recover a set given the sums of all its subsets
There is a set A of positive/negative integers. We are given N numbers which are the sum of all its subsets. The task is to find the set A itself. Following is an example.
Input: 0 -2 4 5 2 3 9 7
...
- 486
2
votes
1
answer
188
views
Efficient way of approaching the Subset Sum Problem with very large input sets
The problem I am facing:
I need to find a way to deal with very large sets (3 to 10000000) of positive and negative ints, this seemed relatively impossible based off of previous experiments.
However, ...
1
vote
1
answer
407
views
Need optimization tips for a subset sum like problem with a big constraint
Given a number 1 <= N <= 3*10^5, count all subsets in the set {1, 2, ..., N-1} that sum up to N. This is essentially a modified version of the subset sum problem, but with a modification that ...
- 13
2
votes
3
answers
1k
views
Find all combinations that add up to given number python with list of lists
I've seen plenty of threads on how to find all combinations that add up to a number with one list, but wanted to know how to expand this such that you can only pick one number at a time, from a list ...
- 156
3
votes
2
answers
968
views
Subset sum problem with known subset size and array being a range
I'm trying to find a fast way to solve the subset sum problem with a few modifications, I know the exact size of the subset I need to get the target number and I also know the input array to be a ...
- 67
0
votes
2
answers
108
views
How Do I Count The Number of Times a Subset of Words Appear In My Pandas Dataframe?
I have a bunch of keywords stored in a 620x2 pandas dataframe seen below. I think I need to treat each entry as its own set, where semicolons separate elements. So, we end up with 1240 sets. Then I'd ...
- 63
2
votes
1
answer
348
views
Efficient way to solve subset sum variation
Given an integer array, find the maximum number of sums of adjacent elements that are divisible by n.
Example 1:
input: long[] array = [1, 2, 3], n = 7
output: 0
Example 2:
input: long[] array = [1, 2,...
- 29
0
votes
0
answers
361
views
Finding all possible unique combinations of numbers to reach a given sum
We have a list of numbers, let's say: [ 2, 3, 5 ]
and we have a targetSum, let's say: 8
Our goal, then, is to pick numbers from the list in such a way that the sum of the numbers would lead to ...
- 147
1
vote
0
answers
213
views
How to get a subset from maximum size subset with given sum solution [C]
I need to find a maximum size subset from a set of numbers which will have a given sum X.
I've found a solution which solves this:
// A Dynamic Programming solution for the
// subset sum problem+ ...
- 99
-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
-3
votes
2
answers
239
views
Subset sum problem with continuous subset using recursion
I am trying to think how to solve the Subset sum problem with an extra constraint: The subset of the array needs to be continuous (the indexes needs to be). I am trying to solve it using recursion in ...
- 799
0
votes
2
answers
360
views
For a Set of Integers, Get All Sets Whose Sum is Greater Than Some Value
Let me start by saying I have found many questions and answers that answer things which seem somewhat related or close to this question, but are not actually this question. It seems related to the ...
- 117
0
votes
0
answers
203
views
Recursively finding subset sum
I am practicing on recursion and i wanted to try a very popular problem for recursion, the subset sum problem, but i wanted a little catch. I also want to print the subset if it exists.
#include <...
1
vote
1
answer
637
views
randomly find a combination from an array with duplicate elements and it's sum equal n
How can I randomly find a combination from an array with duplicate elements and it's sum equal n.
Example
array is [1, 2, 2, 3] and n is 3
answers are 1+2, 1+2, 3
If randomSubsetSum(array, n) is ...
- 346
0
votes
1
answer
263
views
Subset sum problem using key value pairs - python
I have an algorithm that outputs a subset which sums up to a value as close to integer s as possible
from itertools import combinations
products = {
"Apple": 5,
"Pear": 4,
...
0
votes
1
answer
98
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
2
answers
920
views
Subset sum problem for a possible closest value to the target sum in Python for a really big list
I know this problem may have been asked by many. My challenge is that my list is long in length (say 100+) and my target may also be big. The recursive algorithm takes 10 minutes to complete. I need ...
-1
votes
1
answer
65
views
how do i subset many variable in R?
i want to ask how do i subset many data from 5k variable.
i have a 500k data frame, the data was groceries data (super market). i want to subset all the reciept ID, but the ID is too many (about 24,5 ...
1
vote
1
answer
121
views
How to loop over subsets of length k of a list of length n in R?
I am given two numbers n and k with 0 < k < n.
How can I loop over all possible combinations of subsets of length k?
E.g. I have x <- 1:10.
Then I want to do
for (y in c(c(1,2,3), c(1,2,4), c(...
- 305
-1
votes
1
answer
63
views
Minimum Subset Difference code displays wrong output
My minimum subset difference code (Partition a set into two subsets such that the difference of subset sums is minimum) is displaying the wrong output, and I can't understand how. I have gone through ...
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
1
answer
942
views
Count the sum of subsets of size k when the sum is (Greater than or equal to R) or (Lesser than or equal to L)
def knapSack(A,L,R,K,N,Sum):
if(K==0):
if((L>=Sum)or(R<=Sum)):
return 1
else:
return 0
if((N==0)and(K!=0)):
return 0
else:
...
- 11
0
votes
1
answer
192
views
Subset sum decision problem -- how to verify "false" case in polynomial time?
I'm having a bit of trouble understanding how one would verify if there is no solution to a given instance of the subset sum problem in polynomial time.
Of course you could easily verify the positive ...
- 4,859
-1
votes
1
answer
362
views
Python recursion function parameters issue
I'm calling a function inside itself many times to solve the subset sum problem, using as it called, the recursion solution; anyway, I can't figure out why n (which is the number of elements of the ...
1
vote
2
answers
105
views
Trying to understand the time complexity of this dynamic recursive subset sum
# Returns true if there exists a subsequence of `A[0…n]` with the given sum
def subsetSum(A, n, k, lookup):
# return true if the sum becomes 0 (subset found)
if k == 0:
return True
...
- 55
0
votes
2
answers
210
views
How do you find a subarray with the given sum? [duplicate]
I am given an array of elements and the sum K, and I am supposed to find a subarray (doesn’t have to be contiguous) whose sum is equal to K.
For example:
Input: [1, 9, 3, 2, 21], 30
Output: [9, 21]
Do ...
- 39
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
1
answer
46
views
how can i divide a list as subsets which are sum upto given number(non repeat)?
from given list of numbers
nums=[4,3,2,3,5,2,1]
from itertools import combinations
nums=[4,3,2,3,5,2,1]
li=[]
for i in range(1,len(nums)):
comb=combinations(nums,i)
for j in comb:
if ...
0
votes
0
answers
335
views
Problem similar to Coin change problem with finite coins, but with intervallic coin values and fixed number of coins
I have been struggling to create an algorithm, for a problem where we get an array of n coins with their max values. A coin in the array can have a value between 0 and this max value. We want to ...
2
votes
1
answer
619
views
Maximum Sum of elements of array which is not divisible by M, deleting/avoiding at most K consequtive array elements
Given: N, K, M and A(array)
N = No. of elements in the array
K = Maximum consequtive array elements that can be avoided/not considered in the answer
|A| = N
Starting from the last index of the array, ...
2
votes
1
answer
846
views
Use FFT to find all possible fixed-size subset sums
I need to solve the following problem: given an integer sequence x of size N, and a subset size k, find all the possible subset sums. A subset sum is the sum of elements in the subset.
If elements in ...
- 1,680
1
vote
0
answers
103
views
Find smallest set of rows whose column sums at least reach a target
I'm trying to write an algorithm that prints the solution for the following problem:
Given a target array T = [t1, t2, ...
tn], and a set of lists S = { A = [a1,
a2, ... an], B = [b1, b2,
... bn], ......
- 11
0
votes
1
answer
425
views
Subset Sum Problem with constraints and multiple inputs
I'm trying to figure out a way to implement in python a subset sum problem with the constraint that the numbers in the Fixed variable have to always be included.
For Example:
given the following lists:...
1
vote
2
answers
764
views
Algorithm calculate the smallest sum that a number fits into
Given a set of numbers, find the minimum multiple sum that an arbitrary number fits into
number in the set can be used multiple times (or not at all) to achieve a "sum"
the set of numbers ...
- 11
1
vote
1
answer
769
views
Fast Python algorithm for random partitioning with subset sums equal or close to given ratios
This question is an extension of my previous question: Fast python algorithm to find all possible partitions from a list of numbers that has subset sums equal to a ratio
. I want to divide a list of ...
- 2,785
4
votes
1
answer
93
views
Finding the terms of a summation problem that need to be excluded to match the expected sum
I'm trying to automatize/speed up a control process.
The best way to imagine this is like a little store: I know the total that's supposed to be left in the register at the end of the day (e.g. 150$), ...
1
vote
0
answers
109
views
Map subset sum with negative numbers
The subset sum problem is defined as following:
Given a set of positive integers s₁,...,sₙ, is there a subset A of {1,...,n} such that the sum over A gives the positive integer T?
I know that the ...
- 11
0
votes
0
answers
132
views
Subset sum problem with condition on set composition
I have a problem where I am using dynamic programming for a subset sum problem. However here I need to include a condition on the set composition. For example, with a sum of 10 and an array : 3 5 5 7, ...
user14939523
1
vote
0
answers
135
views
Devising optimzed algorithms for restricted-range partition problem
First of all, I'm referring to the 'partition problem' as the decision problem on whether some multiset of positive integers S can be partitioned into two equal-valued subsets. It is known that ...
- 987