Two Sum

Given an array of integers, return indices of the two numbers such that they add up to specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,

return [0, 1].

Solution:

def twoSum(nums, target):

dic = {}

if len(nums) <= 1:

return False

for k in range(len(nums)):

if nums[k] in dic:

return [dic[nums[k]],k]

else:

dic[target - nums[k]] = k


#optimal_Solution #python #data_structure

Number of ways to add up to a sum S with N numbers

Given an array of unique number and sum. There are many combinations and subsets of an array that come up with given sum. 

Example : 

Input : A[] = {1,2,4,5,9}

           sum = 15

Output: 2

Combinations are {1,5,9} and {1,2,4,5}

Input: A[] = {2,3,5,6,8,10}

          Sum = 10 

Output: 3

Combinations are {2,3,5}, {2,8} and {10}

A = [2,3,5,8,10]

total = 10

#initialize all elements to zero first

arr = [[0 for x in range(len(A)+1)] for y in range(len(A)+1)]

arr[0][0] = 1 

index_dict = {0:0} #Stores element and its index in array

for ind, y in enumerate(A):

    index_dict[y] = ind+1

for i in range(1,len(A)+1):

    arr[i] = [x for x in arr[i-1]] #Duplicate upper row

    for j in range(i,len(A)+1):

        diff = A[j-1]-A[i-1]

        if diff in index_dict: #If difference found in present list

            indx = index_dict[diff]

            arr[i][j] = arr[i-1][j] + arr[i-1][indx] #Update with its possible combination

 print arr[-1][-1]      

NA	Array Elements					0
0	2	3	5	8	10	Subtract from
1	0	0	0	0	0	0
1	1	0	0	0	0	2
1	1	1	1	0	0	3
1	1	1	2	1	1	5
1	1	1	2	2	2	8
1	1	1	2	2	3	10

#perfectsumproblem #geeksforgeeks #ways #combinations #subset #subsequence #array #dynamicprogramming