# Combination Sum II Leetcode Solution

In this post, we are going to solve the Combination Sum II Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.

## Problem

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` may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

```Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
```

Example 2:

```Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]
```

Constraints:

• `1 <= candidates.length <= 100`
• `1 <= candidates[i] <= 50`
• `1 <= target <= 30`

Now, lets see the leetcode solution of Combination Sum II Leetcode Solution.

### Combination Sum II Leetcode Solution in Python

```class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []

def dfs(s: int, target: int, path: List[int]) -> None:
if target < 0:
return
if target == 0:
ans.append(path.copy())
return

for i in range(s, len(candidates)):
if i > s and candidates[i] == candidates[i - 1]:
continue
path.append(candidates[i])
dfs(i + 1, target - candidates[i], path)
path.pop()

candidates.sort()
dfs(0, target, [])
return ans
```

### Combination Sum IILeetcode Solutionin CPP

```class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ans;

sort(begin(candidates), end(candidates));
dfs(candidates, 0, target, {}, ans);
return ans;
}

private:
void dfs(const vector<int>& A, int s, int target, vector<int>&& path,
vector<vector<int>>& ans) {
if (target < 0)
return;
if (target == 0) {
ans.push_back(path);
return;
}

for (int i = s; i < A.size(); ++i) {
if (i > s && A[i] == A[i - 1])
continue;
path.push_back(A[i]);
dfs(A, i + 1, target - A[i], move(path), ans);
path.pop_back();
}
}
};
```

### Combination Sum II Leetcode Solution in Java

```class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<>();

Arrays.sort(candidates);
dfs(0, candidates, target, new ArrayList<>(), ans);
return ans;
}

private void dfs(int s, int[] candidates, int target, List<Integer> path,
List<List<Integer>> ans) {
if (target < 0)
return;
if (target == 0) {
return;
}

for (int i = s; i < candidates.length; ++i) {
if (i > s && candidates[i] == candidates[i - 1])
continue;