dynamic_programming.combination_sum_iv

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 “tar”. 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.

Attributes

target

Functions

combination_sum_iv(→ int)

Function checks the all possible combinations, and returns the count

combination_sum_iv_bottom_up(→ int)

Function checks the all possible combinations with using bottom up approach,

combination_sum_iv_dp_array(→ int)

Function checks the all possible combinations, and returns the count

Module Contents

dynamic_programming.combination_sum_iv.combination_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
dynamic_programming.combination_sum_iv.combination_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
dynamic_programming.combination_sum_iv.combination_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
dynamic_programming.combination_sum_iv.target = 5