Zero To DSAZero To DSA
Privacy Policy
PermutationsGenerate Parentheses

Combination Sum

medium
Time: O(2ⁿ)
Space: O(target / min(candidates))

Given an array of distinct integers `candidates` and a target integer `target`, return all unique combinations where candidates sum to target. You may use the same number an unlimited number of times.

Constraints

  • 1 <= candidates.length <= 30
  • All candidates are distinct.

Examples

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