Combination Sum: Finding All Unique Combinations

This challenge focuses on finding all unique combinations of numbers from a given set that add up to a specific target sum. This problem is a classic in algorithmic problem-solving and has applications in areas like dynamic programming and combinatorial mathematics, where you need to explore different ways to achieve a target value using a set of elements.

Problem Description

Given a set of distinct integers candidates and a target integer target, find all unique combinations of numbers from candidates where the chosen numbers sum to target.

Key Requirements:

• The same number from candidates may be chosen an unlimited number of times.
• All numbers (including the target) will be positive integers.
• The solution set must not contain duplicate combinations. Two combinations are considered duplicates if they contain the same numbers with the same frequencies, regardless of order. For example, [2, 3] and [3, 2] are considered the same combination.

Expected Behavior:

Your function should return a list of lists, where each inner list represents a unique combination of numbers from candidates that sums up to target.

Edge Cases to Consider:

• What if no combinations can be found that sum to the target?
• What if the target is 0?
• What if the candidates list is empty?

Examples

Example 1:

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

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

Explanation:
- 2 + 2 + 3 = 7
- 7 = 7
These are the only unique combinations that sum to 7.

Example 2:

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

Output:
[[2, 2, 2, 2], [2, 3, 3], [3, 5]]

Explanation:
- 2 + 2 + 2 + 2 = 8
- 2 + 3 + 3 = 8
- 3 + 5 = 8

Example 3:

Input:
candidates = [1]
target = 2

Output:
[[1, 1]]

Explanation:
- 1 + 1 = 2

Example 4:

Input:
candidates = [8, 2, 4]
target = 11

Output:
[[2, 2, 2, 2, 2, 1], [2, 2, 2, 2, 3], [2, 2, 3, 4], [2, 4, 5], [3, 8]]

Constraints

• 1 <= candidates.length <= 30
• 1 <= candidates[i] <= 200
• 1 <= target <= 500
• All elements in candidates are distinct.

Notes

• Think about how to avoid duplicate combinations. Sorting the candidates array might be helpful.
• Consider using recursion or backtracking as a primary approach.
• The order of numbers within a combination does not matter for uniqueness, but it's good practice to return them in a consistent order (e.g., sorted).
• Be mindful of the "unlimited use" of each candidate number.