Medium

Combination Sum

081

Return unique combinations where candidates can be reused and sum to target. Sort inner and outer lists.

EXAMPLES

Example 1

Input
{
  "candidates": [
    2,
    3,
    6,
    7
  ],
  "target": 7
}

Output
[
  [
    2,
    2,
    3
  ],
  [
    7
  ]
]

FUNCTION SHAPE

candidates: intArraytarget: int→intMatrix

SOLUTION NOTE

We apply the template. This is the same as combinations/subsets. The only difference is we maintain a curr_target, that is basically target - sum(curr). So it refers to how much left we need to reach our target. If it is 0, we are done. That is the base condition of the backtracking. We can prune when curr_target < 0, since all numbers are positive, any further recursion is futile as sum(curr) is already > target. And our recursion is for index j not j+1, since we can re-use the same number multiple times.

Note: we don't actually need to maintain curr_target, since we can just compute sum(curr) every time, but this adds an additional O(n) factor to our runtime.

Reveal reference solution +

pythonREFERENCE

# this returns a unique list of combs without using a set, b/c the initial
# list is distinct integers.
# backtracking(i): tries all possible first choices of combs, from indicies [i, n-1]...
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    n = len(candidates)
    curr = []
    res = []
    curr_target = target

    def backtrack(i):
        nonlocal curr_target
        if curr_target < 0: return
        if curr_target == 0:
            res.append(curr.copy())
        else:
            # try to take every element. recurse on rest
            for j in range(i, n):
                curr.append(candidates[j])
                curr_target -= candidates[j]

                backtrack(j)  # not j+1 !!! since we can re-use j

                curr_target += candidates[j]
                curr.pop()

    backtrack(0)
    return res

TimeO(n*2^n)

SpaceO(n*2^n)

Open on LeetCode ↗