dynamic_programming.combination_sum_iv
======================================

.. py:module:: dynamic_programming.combination_sum_iv

.. autoapi-nested-parse::

   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.



Attributes
----------

.. autoapisummary::

   dynamic_programming.combination_sum_iv.target


Functions
---------

.. autoapisummary::

   dynamic_programming.combination_sum_iv.combination_sum_iv
   dynamic_programming.combination_sum_iv.combination_sum_iv_bottom_up
   dynamic_programming.combination_sum_iv.combination_sum_iv_dp_array


Module Contents
---------------

.. py:function:: 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


.. py:function:: 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


.. py:function:: 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


.. py:data:: target
   :value: 5