********************************************
Combinatorics Problems That Needs Algorithms
********************************************

.. container:: subtitle

  Demonstrated in C++

Why Writing Algorithms?
=======================
+ Prove correctness of your solution using math
+ Too hard to solve using math
+ When we want to see the solution in addition to the count

Typical Approaches
==================
+ Strategy: Other algorithmic paradigms
+ Enumeration problems

  * Simple enumeration: brute force, backtracking
  * With overlapping sub-problems: dynamic programming

+ Optimization problems (Combinatorial optimization)

  * With overlapping sub-problems: greedy algorithm, dynamic programming
  * Without overlapping sub-problems: greedy algorithm
  * Heuristic algorithms: simulated annealing, genetic algorithm, etc.
  * Linear programming

Related C++ Features
====================
+ Recursion

  * art of memorization (manipulate parameter and return value)

+ STL algorithms (``<algorithm>`` header)

  * ``next_permutation`` function
  * ``is_permutation`` function
  * ``sort`` function
  * ``is_sorted`` function
  * ``reverse`` function
  * ``rotate`` function
  * ``shuffle`` function

+ Useful data structures

  * ``std::vector<bool>`` (bitset)

    - to memorize visited/processed/seen states
    - small number of total states
    - :math:`\Theta(1)` time complexity for ``set`` and ``test`` operations

  * ``std::set`` to memorize visited/processed/seen states

    - large number of total states
    - Self-balancing binary search tree
    - :math:`\Theta(\log n)` time complexity for ``insert`` and ``find``
      operations
    - :math:`\Theta(n)` time complexity for ``erase`` operation

  * ``std::unordered_set`` to memorize visited/processed/seen states

    - large number of total states
    - Hash table
    - :math:`\Theta(1)` time complexity for ``insert``, ``find``, and ``erase``
      operations

Enumerate All US Phone Numbers
------------------------------
In this problem, we want to enumerate all US phone numbers.

This is a permutation problem that allow repetition. As an enumeration problem,
we can solve this problem using brute force.

.. code-block:: cpp

  void enumeratePhoneNumbers(int n, string prefix) {
    if (n == 0) {
      cout << prefix << endl;
      return;
    }
    for (int i = 0; i < 10; i++) {
      enumeratePhoneNumbers(n - 1, prefix + to_string(i));
    }
  }

Integer Partition Problem
-------------------------
In this problem we take advantage of the recurrence relation of the integer
partition problem. :math:`p(n, k) = p(n - k, k) + p(n, k - 1)`.

.. code-block:: cpp

  int partition(int n, int k) {
    // Base cases
    if (n == 0) return 1;  // One way to partition 0 using no numbers
    if (n < 0 || k <= 0)
      return 1;  // No way to partition with negative number or no numbers left

    // Recursive cases
    // Include k in the partition and recursively partition n-k with k
    int include_k = partition(n - k, k);

    // Exclude k from the partition and recursively partition n with k-1
    int exclude_k = partition(n, k - 1);

    return include_k + exclude_k;
  }