Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
The same repeated number may be chosen from candidates unlimited number of times.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.
Approach with Depth-First-Search (DFS)
This could be solved with depth-first search algorithms.
But we need to do a optimization for reduce the search space. After sorting the vector, when we enumerate each element in vector, if
(cur_value > target) is true, we could just break out the loop.
Preparing for an interview? Check out this!
Join my Email List for more insights, It's Free!😋