:orphan:

Palindrome Partitioning
=======================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/palindrome-partitioning/

Given a string ``s``, partition ``s`` such that every substring of the
partition is a palindrome. Return *all possible palindrome partitioning
of* ``s``.

 

**Example 1:**

::

   Input: s = "aab"
   Output: [["a","a","b"],["aa","b"]]

**Example 2:**

::

   Input: s = "a"
   Output: [["a"]]

 

**Constraints:**

- ``1 <= s.length <= 16``
- ``s`` contains only lowercase English letters.

.. highlight:: python

Pattern
-------
String, Dynamic Programming, Backtracking

Approaches
----------

.. tab-set::

    .. tab-item:: Backtracking

        **Code**

        .. literalinclude:: ../problems/medium/palindrome-partitioning/palindrome_partitioning__backtracking.py
            :language: python
            :lines: 10-

        **Test**

        >>> from palindrome_partitioning__backtracking import partition
        >>> sorted(partition("aab"))
        [['a', 'a', 'b'], ['aa', 'b']]
        >>> partition("a")
        [['a']]

        .. autofunction:: palindrome_partitioning__backtracking.partition