Variation of twosum implementation

Question

I have a code, given an array and target sum my code returns pair of two integers which add up to the sum. The Python function is as follows

def pairSum2(arr, k):
    if len(arr)<2:
        return
    seen=set()
    output=set()
    for num in arr:
        target=k-num
        if target not in seen:
            seen.add(num)
        else:
            output.add( (min(num, target), max(num, target)) )
    print ('\n'.join( map(str, list(output)) ))

I have to modify it such that given the sum, find out maximum possible combinations in the array which are <= sum:

no more than two numbers can be included in each combination, find out how many such combinations can be made.

I have referred subset sum problem Subset Sum algorithm. How ever this algorithm prints all the subsets which add upto the sum. I am allowed to take <=two numbers at a time.

max heap, min heap can be used. – Ajinkya Jul 21 '18 at 22:57 — Ajinkya, Jul 21 '18 at 22:57

score 0 · Answer 1 · answered Jul 14 '18 at 19:18

0

I hope it helps.
Just sort the array and find the smallest no, say a<=sum. And then , lets have variable i,j,k. j= index of a,count =0

 while(i<j){
 k=j;
 while(k>sum-i && k>i)
 k--;
 //Unique combinations that will give count of pairs having add upto specified 
 //sum
 if(k>i)
 count=count+k-i;
 i++;
 }`

answered Jul 14 '18 at 19:18

Leevansha

11
4

I have considered here duplicates as unique. So kindly check it acc to your ques. – Leevansha Jul 14 '18 at 19:20
No this doesn't answer my question – Ajinkya Jul 14 '18 at 20:19

Variation of twosum implementation

1 Answers1