backtracking.combination_sum
============================

.. py:module:: backtracking.combination_sum

.. autoapi-nested-parse::

   In the Combination Sum problem, we are given a list consisting of distinct integers.
   We need to find all the combinations whose sum equals to target given.
   We can use an element more than one.

   Time complexity(Average Case): O(n!)

   Constraints:
   1 <= candidates.length <= 30
   2 <= candidates[i] <= 40
   All elements of candidates are distinct.
   1 <= target <= 40



Functions
---------

.. autoapisummary::

   backtracking.combination_sum.backtrack
   backtracking.combination_sum.combination_sum
   backtracking.combination_sum.main


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

.. py:function:: backtrack(candidates: list, path: list, answer: list, target: int, previous_index: int) -> None

   A recursive function that searches for possible combinations. Backtracks in case
   of a bigger current combination value than the target value.

   Parameters
   ----------
   previous_index: Last index from the previous search
   target: The value we need to obtain by summing our integers in the path list.
   answer: A list of possible combinations
   path: Current combination
   candidates: A list of integers we can use.


.. py:function:: combination_sum(candidates: list, target: int) -> list

   >>> combination_sum([2, 3, 5], 8)
   [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
   >>> combination_sum([2, 3, 6, 7], 7)
   [[2, 2, 3], [7]]
   >>> combination_sum([-8, 2.3, 0], 1)
   Traceback (most recent call last):
       ...
   RecursionError: maximum recursion depth exceeded


.. py:function:: main() -> None