:orphan:

Subsets
=======

.. highlight:: none

Problem
-------
https://leetcode.com/problems/subsets/

Given an integer array ``nums`` of **unique** elements, return *all
possible* subsets *(the power set)*.

The solution set **must not** contain duplicate subsets. Return the
solution in **any order**.

 

**Example 1:**

::


   Input: nums = [1,2,3]
   Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

**Example 2:**

::


   Input: nums = [0]
   Output: [[],[0]]

 

**Constraints:**

- ``1 <= nums.length <= 10``
- ``-10 <= nums[i] <= 10``
- All the numbers of ``nums`` are **unique**.

.. highlight:: python

Pattern
-------
Array, Backtracking, Bit Manipulation

Solution
--------
We can generate the power set recursively. Every subset of ``nums`` either
includes ``nums[0]`` or it doesn't. If we already have the power set of
``nums[1:]``, we can extend the power set of ``nums`` by taking every subset
:math:`S` of ``nums[1:]`` both as-is and with ``nums[0]`` prepended (including
it):

.. math ::

   P(\texttt{nums}) = P(\texttt{nums[1:]}) \;\cup\; \{ \{\texttt{nums[0]}\} \cup S : S \in P(\texttt{nums[1:]})\}

The base case is the empty array, whose only subset is the empty set.

Code
----

.. literalinclude:: ../problems/medium/subsets/subsets__approach_1.py
    :language: python
    :lines: 13-

Test
----
>>> from subsets__approach_1 import compare_collections, subsets
>>> s = subsets([1, 2, 3])
>>> expected_s = [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]
>>> compare_collections(s, expected_s)
True
>>> s = subsets([0])
>>> expected_s = [[], [0]]
>>> compare_collections(s, expected_s)
True

Complexity
----------
| :math:`n` is the length of the input array
| Time: :math:`O(2^n)` — there are :math:`2^n` subsets of an :math:`n`-element set, and we need to generate each one
| Auxiliary Space: :math:`O(1)`

.. autofunction:: subsets__approach_1.subsets

.. autofunction:: subsets__approach_1.compare_collections