Partition Equal Subset Sum


  • 0
    M

    I solved this problem without recursion.
    Here is my algo :
    canPartition(A)

    1. Check the sum%2, if <>0 then return false where sum=Arrays.stream(A).sum();
    2. Filter out elements which are less than sum/2. Lets assume we have temp[] where each element is less than or equal to sum.
    3. Sort the array. Two variables start =0 and end= temp.length-1, k=sum/2
    4. for i=0 to N in temp,
    5. start=i;
    6. while(k >0 AND start<end)
    7. if checkSum(temp, start, end, k)==true, return true;
    8. else k=k-temp[start++]; loop ends
    9. sum=k, outer loop ends.

    Array is sorted , checkSum(temp, start,end,k) searches for the element in the array from index start to end.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.