40. Combination Sum II

Medium

Problem Description

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.

Examples

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]
]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def combinationSum2(candidates: List[int], target: int) -> List[List[int]]:
    def backtrack(remain: int, start: int, path: List[int]):
        if remain == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]:
                continue  # Skip duplicates
            if candidates[i] > remain:
                break  # Stop if we exceed the target
                
            path.append(candidates[i])
            backtrack(remain - candidates[i], i + 1, path)
            path.pop()
    
    result = []
    candidates.sort()  # Sort to handle duplicates
    backtrack(target, 0, [])
    return result

Java Solution


class Solution {
    public List> combinationSum2(int[] candidates, int target) {
        List> result = new ArrayList<>();
        Arrays.sort(candidates);  // Sort to handle duplicates
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int remain, int start,
                         List path, List> result) {
        if (remain == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;  // Skip duplicates
            }
            if (candidates[i] > remain) {
                break;  // Stop if we exceed the target
            }
            
            path.add(candidates[i]);
            backtrack(candidates, remain - candidates[i], i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }
}

C++ Solution


class Solution {
public:
    vector> combinationSum2(vector& candidates, int target) {
        vector> result;
        vector path;
        sort(candidates.begin(), candidates.end());  // Sort to handle duplicates
        backtrack(candidates, target, 0, path, result);
        return result;
    }
    
private:
    void backtrack(vector& candidates, int remain, int start,
                  vector& path, vector>& result) {
        if (remain == 0) {
            result.push_back(path);
            return;
        }
        
        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;  // Skip duplicates
            }
            if (candidates[i] > remain) {
                break;  // Stop if we exceed the target
            }
            
            path.push_back(candidates[i]);
            backtrack(candidates, remain - candidates[i], i + 1, path, result);
            path.pop_back();
        }
    }
};

JavaScript Solution


/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum2 = function(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b);  // Sort to handle duplicates
    
    const backtrack = (remain, start, path) => {
        if (remain === 0) {
            result.push([...path]);
            return;
        }
        
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i-1]) {
                continue;  // Skip duplicates
            }
            if (candidates[i] > remain) {
                break;  // Stop if we exceed the target
            }
            
            path.push(candidates[i]);
            backtrack(remain - candidates[i], i + 1, path);
            path.pop();
        }
    };
    
    backtrack(target, 0, []);
    return result;
};

C# Solution


public class Solution {
    public IList> CombinationSum2(int[] candidates, int target) {
        var result = new List>();
        Array.Sort(candidates);  // Sort to handle duplicates
        Backtrack(candidates, target, 0, new List(), result);
        return result;
    }
    
    private void Backtrack(int[] candidates, int remain, int start,
                         List path, IList> result) {
        if (remain == 0) {
            result.Add(new List(path));
            return;
        }
        
        for (int i = start; i < candidates.Length; i++) {
            if (i > start && candidates[i] == candidates[i-1]) {
                continue;  // Skip duplicates
            }
            if (candidates[i] > remain) {
                break;  // Stop if we exceed the target
            }
            
            path.Add(candidates[i]);
            Backtrack(candidates, remain - candidates[i], i + 1, path, result);
            path.RemoveAt(path.Count - 1);
        }
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking with duplicate handling. Here's how it works:

Key points: