In the Leetcode Combination Sum II problem 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],
[5]
]
Constraints:
- 1 <= candidates.length <= 100
- 1 <= candidates[i] <= 50
- 1 <= target <= 30
Solution in C Programming
void combinationSum(int* candidate, int size, int target, int index, int* returnSize, int* columnSize, int* element, int** output)
{
if (target == 0) {
int count = 0;
for (int i = 0; i < size; i++) {
if (element[i] == 1) {
count++;
}
}
output[*returnSize] = (int*)malloc(count * sizeof(int));
columnSize[*returnSize] = 0;
for (int i = 0; i < size; i++) {
if (element[i] == 1) {
output[*returnSize][columnSize[*returnSize]++] = candidate[i];
}
}
(*returnSize)++;
} else {
for (int i = index; i < size && target - candidate[i] >= 0; i++) {
if (i == index || candidate[i] != candidate[i - 1]) {
element[i] = 1;
combinationSum(candidate, size, target - candidate[i], i + 1, returnSize, columnSize, element, output);
element[i] = 0;
}
}
}
}
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
*/
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes)
{
int* element = (int*)malloc(candidatesSize * sizeof(int));
*returnColumnSizes = (int*)malloc(1000 * sizeof(int));
for (int i = 0; i < candidatesSize; i++) {
element[i] = 0;
}
*returnSize = 0;
int** output = (int**)malloc(1000 * sizeof(int*));
for (int i = 0; i < candidatesSize; i++) {
for (int j = i + 1; j < candidatesSize; j++) {
if (candidates[j] < candidates[i]) {
int temp = candidates[i];
candidates[i] = candidates[j];
candidates[j] = temp;
}
}
}
combinationSum(candidates, candidatesSize, target, 0, returnSize, *returnColumnSizes, element, output);
return output;
}Solution in C++ Programming
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end());
vector<vector<int>> result;
vector<int> wip;
function<void(int, int)> dfs = [&](int idx, int total) {
for (int i=idx; i<candidates.size(); i++) {
if (i>idx && candidates[i-1] == candidates[i])
continue;
if (total + candidates[i] > target)
break;
wip.push_back(candidates[i]);
total += candidates[i];
if (total == target) {
result.push_back(wip);
} else if (total < target) {
dfs(i+1, total);
}
total -= candidates[i];
wip.pop_back();
}
};
dfs(0, 0);
return result;
}
};Solution in Java Programming
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> paths = new LinkedList<>();
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
//In order to get rid of duplicated elements, we need to sort array first.
Arrays.sort(candidates);
backtrack(candidates, target, 0);
return res;
}
public void backtrack(int[] candidates, int target, int start){
if(sum == target){
res.add(new ArrayList<>(paths));
return;
}
for(int i = start; i < candidates.length && sum + candidates[i] <= target; i++){
//Get rid of duplicated element as the array has been sorted, and it is very important
if(i > start && candidates[i] == candidates[i-1]){
continue;
}
sum += candidates[i];
paths.add(candidates[i]);
backtrack(candidates, target, i + 1);
sum -= candidates[i];
//Get rid of current element as backtracking, and it is very important too
paths.remove(paths.size() - 1);
}
}
}Solution in Python Programming
class Solution:
def helper(self, candidates, currentCombination, combinations, currentIndex, remainingTarget):
# target reaches negative value ignore
if remainingTarget < 0:
return
# we have all the unique combinations that sums up to target
if remainingTarget == 0:
combinations.append(list(currentCombination))
return
# iterate through the index and check for presence of duplicate element which can be done by checking previous index
for index in range(currentIndex,len(candidates)):
if index != currentIndex and candidates[index] == candidates[index - 1]:
continue
currentCombination.append(candidates[index])
self.helper(candidates, currentCombination, combinations, index + 1, remainingTarget - candidates[index])
currentCombination.pop()
def combinationSum2(self, candidates, target):
# sort the given input
candidates.sort()
# result combinations computed will be stored in this list
uniqueCombinations = []
# invoke helper() with following parameters where empty list corresponds to currentCombination which we have
self.helper(candidates, [], uniqueCombinations, 0, target)
return uniqueCombinationsSolution in C# Programming
public class Solution {
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
var counters = new int [51]; // zero index is not used
foreach(var v in candidates) counters[v]++;
var result = new List<IList<int>>();
var stack = new Stack<int>();
Dfs(1, 0);
return result;
void Dfs(int l, int t)
{
if(t == target)
{
result.Add(stack.ToArray());
}
else if(l < counters.Length && t < target)
{
if(counters[l] > 0)
{
counters[l]--;
stack.Push(l);
Dfs(l, t + l);
stack.Pop();
counters[l]++;
}
Dfs(l+1, t);
}
}
}
}Also read,