FAQ Database Discussion Community


Is my recurrence relation right for subset sum?

dynamic-programming,recurrence-relation,subset-sum
Is this recurrence relation correct for the subset sum problem? Statement: Print Yes or No depending on whether there is a subset of the given array a[ ] which sums up to a given number n. dp[i][j] = true, if 0 to j elements in array sum up to i...

Reduce Subset Sum to Polyomino Packing

algorithm,np-complete,subset-sum
This is a homework assignment, so any help is appreciated. I should prove that the following problem is NP-complete. The hint says that you should reduce the subset sum problem to this problem. Given a set of shapes, like the below, and an m-by-n board, decide whether is it possible...

Algorithm for subset-sum with subtraction

python,algorithm,subset-sum
I have a subset-sum problem where you can add or subtract the terms. For instance, if I have five terms (1, 2, 3, 4, 5), I want to know how many ways I can add/subtract the terms to make 7: 3 + 4 2 + 5 1 + 2 +...

Unable to find what's wrong with my code for solve spoj CWC15

algorithm,dynamic-programming,memoization,subset-sum
I am unable to find what's going wrong in both memotization and tabulation for spoj http://www.spoj.com/problems/CWC2015/.If you could point why both codes are giving respective errors that would be really helpful. 1--Memotization Error--time limit exceeded. Don't know why generated random cases and tested on ideone most of the solutions are...

Find all k-size subsets with sum s of an n-size bag of duplicate unsorted positive integers

c#,algorithm,.net-2.0,dynamic-programming,subset-sum
Please note that this is required for a C# .NET 2.0 project (Linq not allowed). I know very similar questions have been asked here and I have already produce some working code (see below) but still would like an advice as to how to make the algorithm faster given k...

Decreasing the run time for my recursive subset sum algorthim

java,algorithm,recursion,big-o,subset-sum
I have a recursive DFS algorithm that correctly counts the amount of subset sums there are. However, the run time for this method is absurd and extremely exponential. For example, when arr contains the set below. The sum we are looking for is 50. The arr has all duplicates and...