#0265

Combination Sum

MediumDSA28 min20 XP

Problem

Given positive candidates and target, return all unique combinations that sum to target. A candidate may be used multiple times. Sort each combination and the final list.

Why This Matters

Combination Sum is the backtracking template for choose, recurse, undo, while controlling duplicate order.

Function Signature

def combination_sum(candidates, target):

Examples

Example 1

Inputcandidates = [2,3,6,7], target = 7

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

2 can be reused, so 2 + 2 + 3 is valid.

Constraints

Return the exact requested value.
Handle edge cases cleanly.
Use the intended DSA pattern when brute force would scale poorly.

CodePython

def combination_sum(candidates, target):
    """
    Input example: candidates = [2,3,6,7], target = 7
    Return: [[2, 2, 3], [7]]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

def combination_sum(candidates, target):
    """
    Input example: candidates = [2,3,6,7], target = 7
    Return: [[2, 2, 3], [7]]
    Return the value from the function so the tests can compare it. Do not print unless the prompt asks.
    """
    # write your code here
    return []

Visible browser tests run here when available.

Testcases2 visible / 3 hidden categories

Reuse allowed

Input[2,3,6,7], target = 7

Expected[[2, 2, 3], [7]]

There are two valid combinations.

Single path

Input[2,3,5], target = 8

Expected[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

The recursion keeps combinations in nondecreasing order.

Hidden Test Categories

no solutiontarget equals one candidatecandidates not sorted