Coding

Combination Sum II

Asked at

InfoEdge India Ltd

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given collection of candidate numbers (candidates) and a integer target.Find all unique combinations in candidates where the sum is equal to the target.There can only be one usage of each number in the candidates combination and return the answer in sorted order.

e.g : The combination [1, 1, 2] and [1, 2, 1] are not unique.

Input : candidates = [2, 1, 2, 7, 6, 1, 5] , target = 8 Output : [ [1, 1, 6] , [1, 2, 5] , [1, 7] , [2, 6] ] Explanation : The combinations sum up to target are 1 + 1 + 6 => 8. 1 + 2 + 5 => 8. 1 + 7 => 8. 2 + 6 => 8.

Input : candidates = [2, 5, 2, 1, 2] , target = 5 Output : [ [1, 2, 2] , [5] ] Explanation : The combinations sum up to target are 1 + 2 + 2 => 5. 5 => 5.

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

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

cpp

class Solution {
public:
    vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
        //your code goes here
    }
};

java

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        //your code goes here
    }
}

python

class Solution:
    def combinationSum2(self, candidates, target):
        #your code goes here

javascript

class Solution {
    combinationSum2(candidates, target) {
        //your code goes here
    }
}

csharp

class Solution {
    public List<List<int>> CombinationSum2(List<int> candidates, int target) {

    }
}

func combinationSum2(candidates []int, target int) [][]int {

}

Stuck? Show a way to structure it+

01Sort candidates.
02Recurse from a start index with remaining target.
03Skip equal values after the first at each depth.
04Recurse from i plus one so an occurrence cannot be reused.
05Emit a copied path at remaining zero.

Reference answer

Sort first, then recurse with start, remaining, and a current combination. At a given recursion depth, iterate i from start; if i is greater than start and candidates[i] equals candidates[i minus one], skip it because choosing either equal occurrence first would generate the same value combination. If the value exceeds remaining, break due to sorting. After choosing index i, recurse with i plus one, not i, because that exact element can be used only once. A later equal element is still available at deeper recursion, so [1, 1, 6] remains possible. When remaining is zero, add a copy of the path. The worst case remains exponential because all valid subsets may be output; sorting costs O(n log n), recursion uses O(n) path space, and result storage is output-sized. Duplicate skipping is per depth, not a global ban on equal values.

Then expect these follow-ups

Why is the duplicate check i greater than start rather than i greater than zero?
Tests: correctness reasoning
How would you return only the number of unique combinations?
Tests: implementation extension

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question