combination_sum_iv.py

"""
Question:
 You are given an array of distinct integers and you have to tell how many
 different ways of selecting the elements from the array are there such that
 the sum of chosen elements is equal to the target number tar.

Example

Input:
 * N = 3
 * target = 5
 * array = [1, 2, 5]

Output:
 9

Approach:
 The basic idea is to go over recursively to find the way such that the sum
 of chosen elements is `target`. For every element, we have two choices

 1. Include the element in our set of chosen elements.
 2. Don't include the element in our set of chosen elements.
"""


defcombination_sum_iv(array: list[int], target: int) ->int:
"""
 Function checks the all possible combinations, and returns the count
 of possible combination in exponential Time Complexity.

 >>> combination_sum_iv([1,2,5], 5)
 9
 """

defcount_of_possible_combinations(target: int) ->int:
iftarget<0:
return0
iftarget==0:
return1
returnsum(count_of_possible_combinations(target-item) foriteminarray)

returncount_of_possible_combinations(target)


defcombination_sum_iv_dp_array(array: list[int], target: int) ->int:
"""
 Function checks the all possible combinations, and returns the count
 of possible combination in O(N^2) Time Complexity as we are using Dynamic
 programming array here.

 >>> combination_sum_iv_dp_array([1,2,5], 5)
 9
 """

defcount_of_possible_combinations_with_dp_array(
target: int, dp_array: list[int]
 ) ->int:
iftarget<0:
return0
iftarget==0:
return1
ifdp_array[target] !=-1:
returndp_array[target]
answer=sum(
count_of_possible_combinations_with_dp_array(target-item, dp_array)
foriteminarray
 )
dp_array[target] =answer
returnanswer

dp_array= [-1] * (target+1)
returncount_of_possible_combinations_with_dp_array(target, dp_array)


defcombination_sum_iv_bottom_up(n: int, array: list[int], target: int) ->int:
"""
 Function checks the all possible combinations with using bottom up approach,
 and returns the count of possible combination in O(N^2) Time Complexity
 as we are using Dynamic programming array here.

 >>> combination_sum_iv_bottom_up(3, [1,2,5], 5)
 9
 """

dp_array= [0] * (target+1)
dp_array[0] =1

foriinrange(1, target+1):
forjinrange(n):
ifi-array[j] >=0:
dp_array[i] +=dp_array[i-array[j]]

returndp_array[target]


if__name__=="__main__":
importdoctest

doctest.testmod()
target=5
array= [1, 2, 5]
print(combination_sum_iv(array, target))