DEV Community

Posted on • Originally published at alkeshghorpade.me

LeetCode - Combination Sum II

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.