Zero To DSAZero To DSA
Privacy Policy路FAQ路Report a Bug路Support on Ko鈥慺i
PermutationsGenerate Parentheses

Combination Sum

medium
Time: O(N^(T/M+1)) where N = candidates, T = target, M = min(candidate)
Space: O(T/M) recursion depth

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]]