Problem statement
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.
Problem statement taken from: https://leetcode.com/problems/combination-sum-ii.
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
Explanation
Backtracking
The problem can be solved using the similar approach we used in our last blog [Combination Sum (https://alkeshghorpade.me/post/leetcode-combination-sum). The only difference is that each element in candidates may only be used once. Using each element only once, can be achieved by jumping to the next index when calling the function recursively.
Another difference is that our solution set must not contain duplicate combinations. The problem statement does not mention the array is sorted. To avoid duplicate result sets, we need to sort the array and avoid using the same elements.
Let's check the algorithm first.
- initialize the result as a 2D array
initialize current as an array
// n = index, at start it will be 0.
// sumTillNow = sum of the current elements in the array, at the start it will be 0
// current = current list of elements in the array, at the start it will be an empty array []
- call combinationSum2Util(result, candidates, current, n, sumTillNow, target)
- return result
// combinationSum2Util function
- if sumTillNow == target
// append current to result
- result.push_back(current)
- if sumTillNow > target
- return
- set prev = -1
- loop for i = n; i <= candidates.size() - 1; i++
- if prev != candidates[i]
// append candidates array ith element to the current array
- current.push_back(candidates[i])
- sumTillNow += candidates[i]
// call the function recursively
- combinationSumUtil(result, candidates, i, target, sumTillNow, current)
- sumTillNow -= current[current.size() - 1]
// remove the last element from the array
- current.pop_back()
- prev = candidates[i]
- end of if
Let's check out our solutions in C++, Golang, and Javascript.
C++ solution
class Solution {
public:
void combinationSum2Util(vector<vector<int>> &result, vector<int>& candidates, vector<int>& current, int index, int sumTillNow, int target) {
if(sumTillNow == target) {
result.push_back(current);
return;
}
if(sumTillNow > target) {
return;
}
int prev = -1;
for(int i = index; i <= candidates.size() - 1; i++) {
if(prev != candidates[i]) {
current.push_back(candidates[i]);
sumTillNow += candidates[i];
combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target);
sumTillNow -= current[current.size() - 1];
current.pop_back();
prev = candidates[i];
}
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> result;
vector<int> current;
sort(candidates.begin(), candidates.end());
combinationSum2Util(result, candidates, current, 0, 0, target);
return result;
}
};
Golang solution
func combinationSum2Util(result *[][]int, candidates, current []int, index, sumTillNow, target int) {
if sumTillNow == target {
*result = append(*result, append([]int{}, current...))
return
}
if sumTillNow > target {
return
}
prev := -1
for i := index; i < len(candidates); i++ {
if prev != candidates[i] {
current = append(current, candidates[i])
sumTillNow += candidates[i]
combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
sumTillNow -= current[len(current) - 1]
current = current[:len(current) - 1]
prev = candidates[i]
}
}
}
func combinationSum2(candidates []int, target int) [][]int {
result := make([][]int, 0)
sort.Ints(candidates)
combinationSum2Util(&result, candidates, []int{}, 0, 0, target)
return result
}
Javascript solution
var combinationSum2 = function(candidates, target) {
let result = [];
candidates.sort(function(a, b){ return a - b });
const combinationSum2Util = (candidates, current, index, sumTillNow, target) => {
if( sumTillNow == target ) {
result.push([...current]);
return;
}
if( sumTillNow > target ) {
return;
}
let prev = -1;
for(let i = index; i < candidates.length; i++) {
if(prev != candidates[i]) {
current.push(candidates[i]);
sumTillNow += candidates[i];
combinationSum2Util(candidates, current, i + 1, sumTillNow, target);
sumTillNow -= current[current.length - 1];
current.pop();
prev = candidates[i];
}
}
}
combinationSum2Util(candidates, [], 0, 0, target);
return result;
};
Let's dry run our algorithm.
Input: candidates = [2, 5, 2, 1, 2]
target = 5
// combinationSum function
Step 1: vector<vector<int>> result
vector<int> current
Step 2: sort(candidates.begin(), candidates.end()
[1, 2, 2, 2, 5]
Step 3: combinationSum2Util(result, candidates, current, 0, 0, target)
// combinationSum2Util function
Step 4: if sumTillNow == target
0 == 5
false
if sumTillNow > target
0 > 5
false
prev = -1
loop for int i = index; i <= candidates.size() - 1
i = 0
0 <= 5 - 1
true
- if prev != candidates[i]
-1 != 1
true
current.push_back(candidates[i])
current.push_back(candidates[0])
current.push_back(1)
current = [1]
sumTillNow += candidates[i]
= sumTillNow + candidates[0]
= 0 + 1
= 1
combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
combinationSum2Util([][], [1, 2, 2, 2, 5], [1], 1, 1, 5)
Step 5: if sumTillNow == target
1 == 5
false
if sumTillNow > target
1 > 5
false
prev = -1
loop for int i = index; i <= candidates.size() - 1
i = 1
1 <= 5 - 1
true
- if prev != candidates[i]
-1 != 2
true
current.push_back(candidates[i])
current.push_back(candidates[1])
current.push_back(2)
current = [1, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[1]
= 1 + 2
= 3
combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 2], 3, 3, 5)
Step 6: if sumTillNow == target
3 == 5
false
if sumTillNow > target
3 > 5
false
prev = -1
loop for int i = index; i <= candidates.size() - 1
i = 2
2 <= 5 - 1
true
- if prev != candidates[i]
-1 != 2
true
current.push_back(candidates[i])
current.push_back(candidates[1])
current.push_back(2)
current = [1, 2, 2]
sumTillNow += candidates[i]
= sumTillNow + candidates[1]
= 3 + 2
= 5
combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 2, 2], 3, 5, 5)
Step 7: if sumTillNow == target
5 == 5
true
result.push_back(current)
result = [[1, 2, 2]]
return
we backtrack to step 6 and continue
Step 8: combinationSumUtil([][], [1, 2, 2, 2, 5], [1, 2, 2], 3, 5, 5)
sumTillNow = sumTillNow - current[current.size() - 1]
= 5 - current[3 - 1]
= 5 - current[2]
= 5 - 2
= 3
current.pop_back()
current = [1, 2]
prev = candidates[i]
= candidates[2]
= 2
i++
i = 3
loop for int i = index; i <= candidates.size() - 1
i = 3
3 <= 5 - 1
true
- if prev != candidates[3]
2 != 2
false
i++
i = 4
loop for int i = index; i <= candidates.size() - 1
i = 3
4 <= 5 - 1
true
- if prev != candidates[4]
2 != 5
true
current.push_back(candidates[i])
current.push_back(candidates[4])
current.push_back(5)
current = [1, 2, 5]
sumTillNow += candidates[i]
= sumTillNow + candidates[4]
= 3 + 5
= 8
combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
combinationSum2Util([][], [1, 2, 2, 2, 5], [5], 5, 8, 5)
Step 9: if sumTillNow == target
8 == 5
false
if sumTillNow > target
8 > 5
true
return
we backtrack to step 5 and continue
Step 10: combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 2], 3, 3, 5)
sumTillNow = sumTillNow - current[current.size() - 1]
= 3 - current[2 - 1]
= 3 - current[1]
= 3 - 2
= 1
current.pop_back()
current = [1]
prev = candidates[i]
= candidates[1]
= 2
i++
i = 2
loop for int i = index; i <= candidates.size() - 1
i = 2
2 <= 5 - 1
true
- if prev != candidates[3]
2 != 2
false
i++
i = 3
loop for int i = index; i <= candidates.size() - 1
i = 3
3 <= 5 - 1
true
- if prev != candidates[3]
2 != 2
false
i++
i = 4
loop for int i = index; i <= candidates.size() - 1
i = 4
4 <= 5 - 1
true
- if prev != candidates[4]
2 != 5
true
current.push_back(candidates[i])
current.push_back(candidates[4])
current.push_back(5)
current = [1, 5]
sumTillNow += candidates[i]
= sumTillNow + candidates[4]
= 1 + 5
= 6
combinationSum2Util(result, candidates, current, i + 1, sumTillNow, target)
combinationSum2Util([][], [1, 2, 2, 2, 5], [1, 5], 5, 6, 5)
Step 11: if sumTillNow == target
6 == 5
false
if sumTillNow > target
6 > 5
true
return
we backtrack to step 4 and continue
We similarly iterate from index 2, backtrack, and then reach the last index.
We return the answer as
[
[1, 2, 2],
[5]
]
Top comments (0)