Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates can only be used once in the combination.
public class Solution {
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
List<IList<int>> ans = new List<IList<int>>();
Array.Sort(candidates);
BackTrack(candidates,0, target,new List<int>(), ans);
return ans;
}
public void BackTrack(int[] cand, int start,int target,List<int> list, List<IList<int>> result)
{
if (target < 0)
return;
if (target == 0)
result.Add(new List<int>(list));
for (int i = start; i < cand.Length; i++)
{
if (i > start && cand[i] == cand[i - 1])
continue; // skip duplicates
list.Add(cand[i]);
BackTrack(cand, i+1, target - cand[i], list, result);
list.RemoveAt(list.Count-1);
}
}
}