Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.
Each number in candidates may only be used once in the combination.
Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations.
Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[1, 2, 5],
[1, 1, 6]
Approach with Depth-First-Search (DFS)
This challenge is a variant of previous one: LeetCode: Combination Sum.
We can use the same algorithm(DFS) to solve it, one difference is we can not use one element multiple times, so we increment the index in next iteration.
Another point need to notice, the exists duplicate elements in input, so we need to use
set<vector<int> > vec_set to remove duplicates in result.
Preparing for an interview? Check out this!