CODEWITHSUNDEEP
algorithmdynamic-programmingnp-completesubset-sum
Max Frost
Max Frost

Reputation: 19

Finding the maximum sum that can be formed from a set, by partitioning it into two subset

Decription

Given a set of numbers S.
Find maximum sum such that
Sum(A1) = Sum(A2)
Where, A1⊂S and A2⊂S and A1⋂A2=∅
And Sum(X), is the sum of all elements within the set X.

Approach

Brute Force

The easiest approach is:

print maximumSum(0,0,0)
def maximumSum(index,sum1,sum2):
  ans=0
  if sum1 == sum2:
    ans=sum1
  if index >= len(S):
    return ans
  m1=maximumSum(index+1,sum1+S[index],sum2)
  m2=maximumSum(index+1,sum1,sum2+S[index])
  m3=maximumSum(index+1,sum1,sum2)
  return max(m,m1,m2,m3)

Time Complexity:O(2N)
Space Complexity:O(1)

Is there a better approach than this?
Optional:
I would like to know whether the given problem is an NP-Complete problem or not.

Edit:

Limits

1 <= Sum(S) <= 1000000
2 <= len(S) <= 100
Time Limit: 60sec(can vary depending upon language used)

Upvotes: 1

Views: 1021

Answers (1)

shole
shole

Reputation: 4084

Yes It is NPC problem Partition Problem

You can see the pseudo polynomial algorithm part if the sum of the set is small

Upvotes: 1

Related Questions