304 North Cardinal St.
Dorchester Center, MA 02124

# Combination Sum II LeetCode Solution

## Problem – Combination Sum II LeetCode Solution

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],

]
``````

Constraints:

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

## Combination Sum II LeetCode Solution in Java

`````` public List<List<Integer>> combinationSum2(int[] cand, int target) {
Arrays.sort(cand);
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
dfs_com(cand, 0, target, path, res);
return res;
}
void dfs_com(int[] cand, int cur, int target, List<Integer> path, List<List<Integer>> res) {
if (target == 0) {
return ;
}
if (target < 0) return;
for (int i = cur; i < cand.length; i++){
if (i > cur && cand[i] == cand[i-1]) continue;
dfs_com(cand, i+1, target - cand[i], path, res);
path.remove(path.size()-1);
}
}
``````

## Combination Sum II LeetCode Solution in Python

``````def combinationSum2(self, candidates, target):
# Sorting is really helpful, se we can avoid over counting easily
candidates.sort()
result = []
self.combine_sum_2(candidates, 0, [], result, target)
return result

def combine_sum_2(self, nums, start, path, result, target):
# Base case: if the sum of the path satisfies the target, we will consider
# it as a solution, and stop there
if not target:
result.append(path)
return

for i in xrange(start, len(nums)):
# Very important here! We don't use `i > 0` because we always want
# to count the first element in this recursive step even if it is the same
# as one before. To avoid overcounting, we just ignore the duplicates
# after the first element.
if i > start and nums[i] == nums[i - 1]:
continue

# If the current element is bigger than the assigned target, there is
# no need to keep searching, since all the numbers are positive
if nums[i] > target:
break

# We change the start to `i + 1` because one element only could
# be used once
self.combine_sum_2(nums, i + 1, path + [nums[i]],
result, target - nums[i])
``````

## Combination Sum II LeetCode Solution in C++

``````class Solution {
public:
vector<vector<int> > combinationSum2(vector<int> &num, int target)
{
vector<vector<int>> res;
sort(num.begin(),num.end());
vector<int> local;
findCombination(res, 0, target, local, num);
return res;
}
void findCombination(vector<vector<int>>& res, const int order, const int target, vector<int>& local, const vector<int>& num)
{
if(target==0)
{
res.push_back(local);
return;
}
else
{
for(int i = order;i<num.size();i++) // iterative component
{
if(num[i]>target) return;
if(i&&num[i]==num[i-1]&&i>order) continue; // check duplicate combination
local.push_back(num[i]),
findCombination(res,i+1,target-num[i],local,num); // recursive componenet
local.pop_back();
}
}
}
};
``````
##### Combination Sum II LeetCode Solution Review:

In our experience, we suggest you solve this Combination Sum II LeetCode Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Combination Sum II LeetCode Solution

Find on Leetcode

##### Conclusion:

I hope this Combination Sum II LeetCode Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

LeetCode Solutions

Hacker Rank Solutions

CodeChef Solutions