This is almost the same as problem 39. Combination Sum. The only difference is that one number can only be used once.
So we could do a DFS to find the target number. During the DFS process, we should keep the path. And once we get an zero, we copy the current path and add it to the result.
To avoid duplicate, we only search for children which is greater than current node.
And note that, for candidates like [1, 1, 2, 5], we don't need to gothrough the path where second "1" is the first value. Because the result is the same as where the first "1" is in the first position.
class Solution: def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]: candidates.sort() self.ans =  path =  self._helper(target, 0, candidates, path) return self.ans def _helper(self, target, start, candidates, path): if target == 0: self.ans.append(path[:]) return elif target < 0: return prev = None for i in range(start, len(candidates)): if candidates[i] == prev: continue prev = candidates[i] path.append(candidates[i]) self._helper(target - candidates[i], i + 1, candidates, path) path.pop()