Loading problem...
You are given an array of unique positive integers called candidates and a positive integer target. Your task is to find and return all distinct ways to select numbers from candidates such that the selected numbers add up exactly to the target value.
The key characteristic of this problem is that the same number can be selected multiple times from the candidates array. This means each candidate can appear any number of times (including zero) in a single combination.
Two combinations are considered different if at least one number appears with a different frequency between them. The combinations can be returned in any order, and the numbers within each combination can also appear in any order.
The test cases are designed such that the total number of valid combinations will not exceed 150 for any given input.
candidates = [2,3,6,7]
target = 7[[2,2,3],[7]]There are exactly two ways to reach the target sum of 7: • Using 2 twice and 3 once: 2 + 2 + 3 = 7 • Using 7 once: 7 = 7 Note that 2 can be reused as many times as needed within a single combination.
candidates = [2,3,5]
target = 8[[2,2,2,2],[2,3,3],[3,5]]Three valid combinations sum to 8: • 2 + 2 + 2 + 2 = 8 (using 2 four times) • 2 + 3 + 3 = 8 (using 2 once and 3 twice) • 3 + 5 = 8 (using each once)
candidates = [2]
target = 1[]The smallest candidate is 2, which already exceeds the target of 1. Therefore, no combination can possibly sum to 1, resulting in an empty list.
Constraints