:orphan:

Combination Sum II
==================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/combination-sum-ii/

Given a collection of candidate numbers (``candidates``) and a target
number (``target``), find all unique combinations in
``candidates`` where the candidate numbers sum to ``target``.

Each number in ``candidates`` may only be used **once** in the
combination.

**Note:** The solution set must not contain duplicate combinations.

 

**Example 1:**

::


   Input: candidates = [10,1,2,7,6,1,5], target = 8
   Output: 
   [
   [1,1,6],
   [1,2,5],
   [1,7],
   [2,6]
   ]

**Example 2:**

::


   Input: candidates = [2,5,2,1,2], target = 5
   Output: 
   [
   [1,2,2],
   [5]
   ]

 

**Constraints:**

- ``1 <= candidates.length <= 100``
- ``1 <= candidates[i] <= 50``
- ``1 <= target <= 30``

.. highlight:: python

Pattern
-------
Array, Backtracking

Approaches
----------

.. tab-set::

    .. tab-item:: Backtracking

        **Code**

        .. literalinclude:: ../problems/medium/combination-sum-ii/combination_sum_ii__backtracking.py
            :language: python
            :lines: 10-

        **Test**

        >>> from combination_sum_ii__backtracking import combinationSum2
        >>> sorted([sorted(c) for c in combinationSum2([10, 1, 2, 7, 6, 1, 5], 8)])
        [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
        >>> sorted([sorted(c) for c in combinationSum2([2, 5, 2, 1, 2], 5)])
        [[1, 2, 2], [5]]

        .. autofunction:: combination_sum_ii__backtracking.combinationSum2