'''

    Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in
    C where the candidate numbers sums to T.

    The same repeated number may be chosen from C unlimited number of times.

    Note:
        All numbers (including target) will be positive integers.
        The solution set must not contain duplicate combinations.

    Link: https://leetcode.com/problems/combination-sum/?tab=Description

    Example:
        For example, given candidate set [2, 3, 6, 7] and target 7,

        A solution set is:
        [
          [7],
          [2, 2, 3]
        ]

    Solution:
        We first sort the array from small to big. For each number in the sorted array, we consider EITHER including it
        (so target-=input[0] and array doesn't change) OR not including it (so target stays same, but array removes the
        first element).

        Throughout the recursion, we consider 3 edge cases:
            1.target>array[0]
            2.array==[]
            3.target==array[0].

            In the first 2 cases, it returns a []. In case 3, it returns [array[0]]

    Source: https://discuss.leetcode.com/topic/81514/python-solution-that-beats-96-by-sorting-the-input-first

'''

class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        legos = sorted(candidates)

        def helper(lego, target):
            if lego == []:
                return []
            if target < lego[0]:
                return []
            if target == lego[0]:
                return [[lego[0]]]
            return [[lego[0]] + a for a in helper(lego, target - lego[0])] + helper(lego[1:], target)

        return helper(legos, target)
