Implement the combinationSumCount method that counts combinations that can sum to the target.
The input contains an integer array nums, its size, and a target value.
Your task is to count how many unique combinations can be formed where selected numbers add up to the target. A number may be used more than once in a combination.
For example, with [2,3,6,7] and target 7, the valid combinations are [7] and [2,2,3], so the answer is 2.
Example 1
[2,3,6,7]472Example 2
[2,3,5]383Example 3
[2]110Use backtracking to try possible combinations.
Start from an index and repeatedly choose a candidate number. To allow the same number again, continue the recursive call from the same index after choosing it. To avoid counting the same combination in a different order, never go back to earlier indexes.
When the remaining target becomes 0, one valid combination has been found. If it becomes negative, stop that path.
Pseudocode:
function combinationSumCount(nums, size, target):
count = 0
backtrack(startIndex, remaining):
if remaining == 0:
count++
return
if remaining < 0:
return
for i from startIndex to size - 1:
backtrack(i, remaining - nums[i])
backtrack(0, target)
return count