Combination Sum - aloalgo
aloalgo logoaloalgo
Beta
Problems
Login

Combination Sum

Medium

You are given an array of distinct integers candidates and a single integer target.

Your task is to find all unique combinations of numbers from candidates such that their sum equals target.

You may assume that:

  • Each number in candidates may be chosen an unlimited number of times.
  • The numbers in candidates are distinct.

Return a list of these unique combinations. The order of combinations in the output does not matter, and the order of numbers within a combination does not matter.

Example 1

Inputs
candidates = [1, 2, 3]
target = 4
Output
[
  [1, 1, 1, 1],
  [1, 1, 2],
  [1, 3],
  [2, 2]
]
Explanation:

The combinations are (1,1,1,1) because 1 + 1 + 1 + 1 = 4, (1,1,2) because 1 + 1 + 2 = 4, (1,3) because 1 + 3 = 4, and (2,2) because 2 + 2 = 4. All are unique.

Example 2

Inputs
candidates = [2, 3, 4]
target = 7
Output
[
  [2, 2, 3],
  [3, 4]
]
Explanation:

The combinations are (2,2,3) because 2 + 2 + 3 = 7, and (3,4) because 3 + 4 = 7. All are unique.

Example 3

Inputs
candidates = [2]
target = 3
Output
[
  
]
Explanation:

There are no combinations that sum to 3 using only the number 2.

Loading...
Case 1Case 2Case 3
Inputs
candidates = [1, 2, 3]
target = 4
Output
[
  [1, 1, 1, 1],
  [1, 1, 2],
  [1, 3],
  [2, 2]
]
🤖

Hello! I am your ✨ AI assistant. I can provide you hints, explanations, give feedback on your code, and more. Just ask me anything related to the problem you're working on!