40. Combination Sum II - Solution & Explanation

The problem

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

Approach overview

Problem Overview: Given an integer array candidates and a target value, return all unique combinations where the chosen numbers sum to the target. Each number can be used at most once, and duplicate combinations must be avoided even if the input contains repeated values.

Approach 1: Backtracking with Sorting and Pruning (Time: O(2^n), Space: O(n))

This problem fits naturally with backtracking. Start by sorting the array so duplicates sit next to each other. Recursively build combinations while tracking the remaining target. At each step you iterate forward from the current index, choose a candidate, subtract it from the remaining target, and continue exploring deeper. If the remaining target becomes zero, you record the current path as a valid combination.

The key detail is duplicate elimination. When iterating through candidates, skip elements that are the same as the previous element at the same recursion depth (if i > start and nums[i] == nums[i-1]). Sorting enables this check and prevents generating identical combinations like [1,2,5] multiple times. Another optimization is pruning: once the current number exceeds the remaining target, you stop exploring that branch because further numbers will only be larger.

This approach works well because the search space shrinks quickly after sorting and pruning. The recursion depth is at most n, and the algorithm only explores valid candidate paths instead of brute-forcing every subset.

Approach 2: Dynamic Programming (Time: O(n * target * k), Space: O(n * target))

A dynamic programming variant can also generate combinations that sum to the target. The idea is similar to subset sum. Build a DP table where dp[s] stores combinations that produce sum s. Iterate through the candidates and update the table from target down to the candidate value to ensure each element is used only once.

When updating the table, append the current candidate to combinations that previously formed s - candidate. Because the array may contain duplicates, sorting and careful state handling are required to avoid repeated result sets. While this method systematically builds solutions, it typically consumes more memory because it stores many intermediate combinations.

The DP approach is useful when the target value is relatively small and you want a structured bottom-up solution. However, managing duplicates and combination storage makes it less common in interviews.

Recommended for interviews: The expected solution is the backtracking approach. Interviewers want to see that you recognize the subset-generation pattern, sort the array, skip duplicates, and prune early when the remaining sum becomes negative. A brute-force subset enumeration shows basic understanding, but optimized backtracking with duplicate handling demonstrates strong control of recursion and search pruning. The problem mainly tests skills in array manipulation and recursive exploration.

Approach 1: Backtracking Approach

The primary idea here is to use a backtracking algorithm to explore all potential combinations of numbers that sum up to the target value. By sorting the array first, we can avoid duplicate combinations by skipping over duplicates within the loop. This ensures each combination is unique, as indicated in the problem statement.

Python

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def backtrack(start, target, path):
            if target == 0:
                result.append(path)
                return
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                if candidates[i] > target:
                    break
                backtrack(i + 1, target - candidates[i], path + [candidates[i]])

        candidates.sort()
        result = []
        backtrack(0, target, [])
        return result

Java

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> list = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(list, new ArrayList<>(), candidates, target, 0);
        return list;
    }

    private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] nums, int remain, int start) {
        if (remain < 0) return;
        else if (remain == 0) list.add(new ArrayList<>(tempList));
        else {
            for (int i = start; i < nums.length; i++) {
                if (i > start && nums[i] == nums[i - 1]) continue;
                tempList.add(nums[i]);
                backtrack(list, tempList, nums, remain - nums[i], i + 1);
                tempList.remove(tempList.size() - 1);
            }
        }
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> ans;
        vector<int> temp;
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, ans, temp, 0);
        return ans;
    }

    void backtrack(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& temp, int start) {
        if (target == 0) {
            ans.push_back(temp);
            return;
        }
        for (int i = start; i < candidates.size(); i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            if (candidates[i] > target) break;
            temp.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], ans, temp, i + 1);
            temp.pop_back();
        }
    }
};

JavaScript

var combinationSum2 = function(candidates, target) {
    candidates.sort((a, b) => a - b);
    const result = [];

    function backtrack(start, target, path) {
        if (target === 0) {
            result.push([...path]);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i - 1]) continue;
            if (candidates[i] > target) break;
            path.push(candidates[i]);
            backtrack(i + 1, target - candidates[i], path);
            path.pop();
        }
    }

    backtrack(0, target, []);
    return result;
};

#include <stdio.h>
#include <stdlib.h>

void backtrack(int* candidates, int candidatesSize, int* result, int resultSize, int** returnColumnSizes, int* temp, int tempSize, int target, int startIndex, int* returnSize) {
    if (target == 0) {
        (*returnColumnSizes)[*returnSize] = tempSize;
        result[*returnSize] = malloc(tempSize * sizeof(int));
        for (int i = 0; i < tempSize; i++) {
            result[*returnSize][i] = temp[i];
        }
        (*returnSize)++;
        return;
    }
    for (int i = startIndex; i < candidatesSize; i++) {
        if (i > startIndex && candidates[i] == candidates[i-1]) continue;
        if (candidates[i] > target) break;
        temp[tempSize] = candidates[i];
        backtrack(candidates, candidatesSize, result, candidatesSize, returnColumnSizes, temp, tempSize + 1, target - candidates[i], i + 1, returnSize);
    }
}

int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) {
    qsort(candidates, candidatesSize, sizeof(int), cmpfunc);
    int** result = malloc(1000 * sizeof(int*));
    *returnColumnSizes = malloc(1000 * sizeof(int));
    int temp[1000];
    *returnSize = 0;
    backtrack(candidates, candidatesSize, result, candidatesSize, returnColumnSizes, temp, 0, target, 0, returnSize);
    return result;
}

int cmpfunc(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
        Array.Sort(candidates);
        List<IList<int>> results = new List<IList<int>>();
        List<int> combination = new List<int>();
        Backtrack(results, combination, candidates, target, 0);
        return results;
    }

    private void Backtrack(List<IList<int>> results, List<int> combination, int[] candidates, int target, int start) {
        if (target == 0) {
            results.Add(new List<int>(combination));
            return;
        }
        for (int i = start; i < candidates.Length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            if (candidates[i] > target) break;
            combination.Add(candidates[i]);
            Backtrack(results, combination, candidates, target - candidates[i], i + 1);
            combination.RemoveAt(combination.Count - 1);
        }
    }
}

The Python solution uses backtracking after sorting the candidates.
Backtracking helps in exploring all combinations while avoiding duplicates via sorted array.
Recurrence is called while decrementing the target by candidates values.

Complexity

Time Complexity: O(2^n), with n being the length of the candidates list.

Space Complexity: O(n) due to recursion stack usage.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

In this approach, we use a variation of the dynamic programming (DP) paradigm referred to as memoization. Instead of exploring each possibility outright, the DP technique seeks to store the results of previously computed states, allowing reuse and thus reducing redundant calculations. Although it's less intuitive than the backtracking approach, it can provide improved efficiency by leveraging prior knowledge.

This approach may involve defining a recursive function with the current state being a pair of active indices and remaining targets, ensuring we cover all combinations.

Python

/* Python implementation benefits from functional programming for memoization */

Java

/* Java implementation relies on hash maps for memoization */

C++

/* C++ DP implementation similar to backtracking but using memory caching */

JavaScript

/* JavaScript employs objects or ES6 maps to serve as caches in the DP variant */

/* C code for DP approach not included due to complexity */

/* C# leverages Dictionary or similar structures for caching in DP approach */

Python allows use of decorators or built-in libraries to easily cache results of functions.
This approach substitutes repeated subproblem evaluations with simple lookups, resulting in performance improvements.

Complexity

Time Complexity: Contextual, based on the efficiency of cache access.

Space Complexity: Higher due to cached results storage.

Try this approach in the editor

Approach 3: Sorting + Pruning + Backtracking

We can first sort the array to facilitate pruning and skipping duplicate numbers.

Next, we design a function dfs(i, s), which means starting the search from index i with a remaining target value of s. Here, i and s are both non-negative integers, the current search path is t, and the answer is ans.

In the function dfs(i, s), we first check whether s is 0. If it is, we add the current search path t to the answer ans, and then return. If i geq n or s \lt candidates[i], the path is invalid, so we return directly. Otherwise, we start the search from index i, and the search index range is j \in [i, n), where n is the length of the array candidates. During the search, if j \gt i and candidates[j] = candidates[j - 1], it means that the current number is the same as the previous number, we can skip the current number because the previous number has been searched. Otherwise, we add the current number to the search path t, recursively call the function dfs(j + 1, s - candidates[j]), and after the recursion ends, we remove the current number from the search path t.

We can also change the implementation logic of the function dfs(i, s) to another form. If we choose the current number, we add the current number to the search path t, then recursively call the function dfs(i + 1, s - candidates[i]), and after the recursion ends, we remove the current number from the search path t. If we do not choose the current number, we can skip all numbers that are the same as the current number, then recursively call the function dfs(j, s), where j is the index of the first number that is different from the current number.

In the main function, we just need to call the function dfs(0, target) to get the answer.

The time complexity is O(2^n times n), and the space complexity is O(n). Here, n is the length of the array candidates. Due to pruning, the actual time complexity is much less than O(2^n times n).

Approach 4: Sorting + Pruning + Backtracking(Another Form)

TypeScript

function combinationSum2(candidates: number[], target: number): number[][] {
    candidates.sort((a, b) => a - b);
    const ans: number[][] = [];
    const t: number[] = [];
    const dfs = (i: number, s: number) => {
        if (s === 0) {
            ans.push(t.slice());
            return;
        }
        if (i >= candidates.length || s < candidates[i]) {
            return;
        }
        const x = candidates[i];
        t.push(x);
        dfs(i + 1, s - x);
        t.pop();
        while (i < candidates.length && candidates[i] === x) {
            ++i;
        }
        dfs(i, s);
    };
    dfs(0, target);
    return ans;
}

func combinationSum2(candidates []int, target int) (ans [][]int) {
	sort.Ints(candidates)
	t := []int{}
	var dfs func(i, s int)
	dfs = func(i, s int) {
		if s == 0 {
			ans = append(ans, slices.Clone(t))
			return
		}
		if i >= len(candidates) || s < candidates[i] {
			return
		}
		for j := i; j < len(candidates); j++ {
			if j > i && candidates[j] == candidates[j-1] {
				continue
			}
			t = append(t, candidates[j])
			dfs(j+1, s-candidates[j])
			t = t[:len(t)-1]
		}
	}
	dfs(0, target)
	return
}

Rust

impl Solution {
    fn dfs(mut i: usize, s: i32, candidates: &Vec<i32>, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>) {
        if s == 0 {
            ans.push(t.clone());
            return;
        }
        if i >= candidates.len() || s < candidates[i] {
            return;
        }
        let x = candidates[i];
        t.push(x);
        Self::dfs(i + 1, s - x, candidates, t, ans);
        t.pop();
        while i < candidates.len() && candidates[i] == x {
            i += 1;
        }
        Self::dfs(i, s, candidates, t, ans);
    }

    pub fn combination_sum2(mut candidates: Vec<i32>, target: i32) -> Vec<Vec<i32>> {
        candidates.sort();
        let mut ans = Vec::new();
        Self::dfs(0, target, &candidates, &mut vec![], &mut ans);
        ans
    }
}

PHP

class Solution {
    /**
     * @param integer[] $candidates
     * @param integer $target
     * @return integer[][]
     */

    function combinationSum2($candidates, $target) {
        $result = [];
        $currentCombination = [];
        $startIndex = 0;

        sort($candidates);
        $this->findCombinations($candidates, $target, $startIndex, $currentCombination, $result);
        return $result;
    }

    function findCombinations($candidates, $target, $startIndex, $currentCombination, &$result) {
        if ($target === 0) {
            $result[] = $currentCombination;
            return;
        }

        for ($i = $startIndex; $i < count($candidates); $i++) {
            $num = $candidates[$i];
            if ($num > $target) {
                break;
            }

            if ($i > $startIndex && $candidates[$i] === $candidates[$i - 1]) {
                continue;
            }
            $currentCombination[] = $num;

            $this->findCombinations(
                $candidates,
                $target - $num,
                $i + 1,
                $currentCombination,
                $result,
            );
            array_pop($currentCombination);
        }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Backtracking Approach	Time Complexity: O(2^n), with n being the length of the candidates list. Space Complexity: O(n) due to recursion stack usage.
Dynamic Programming Approach	Time Complexity: Contextual, based on the efficiency of cache access. Space Complexity: Higher due to cached results storage.
Sorting + Pruning + Backtracking	–
Sorting + Pruning + Backtracking(Another Form)	–

Complexity analysis

Approach	Time	Space	When to Use
Backtracking with Sorting	O(2^n)	O(n)	Best general solution; handles duplicates cleanly with pruning
Backtracking with Pruning	O(2^n) worst case but faster in practice	O(n)	Preferred in interviews when the array is sorted and early stopping is possible
Dynamic Programming (Subset Sum style)	O(n * target * k)	O(n * target)	Useful when target is small and you want a bottom-up combination-building approach

Frequently asked questions

Is Combination Sum II easy or hard?

Combination Sum II is classified as a Medium difficulty problem. The recursion itself is straightforward, but correctly handling duplicates and pruning search branches is the main challenge. Candidates who are comfortable with backtracking patterns typically solve it quickly.

Combination Sum II Python/Java solution

Most implementations follow the same pattern: sort the array, run a recursive backtracking function, skip duplicate values at the same recursion depth, and stop exploring when the remaining target becomes negative. This logic translates directly across Python, Java, C++, C#, and JavaScript with minimal structural differences.

How to solve Combination Sum II in O(n)?

An O(n) solution is not feasible because the problem requires enumerating all valid combinations. The number of valid combinations itself can be exponential in the worst case. The most efficient practical solution uses backtracking with pruning and duplicate skipping, which significantly reduces unnecessary exploration but still has O(2^n) worst-case complexity.

What is the best approach for Combination Sum II?

Backtracking with sorting and duplicate skipping is the most effective solution. Sorting allows you to detect repeated numbers and avoid generating identical combinations. The recursion explores candidate choices while pruning branches where the remaining target becomes negative. This approach runs in O(2^n) time in the worst case with O(n) recursion stack space.

Is Combination Sum II asked at Google/Amazon/Meta?

Combination Sum style problems frequently appear in interviews at companies like Amazon, Google, and Meta because they test recursive thinking and pruning strategies. Variants of this problem are commonly used to evaluate backtracking skills, duplicate handling, and efficient search space reduction.

What data structure is used in Combination Sum II?

The core structure is an array combined with recursion and a dynamic list to store the current combination path. Sorting the array helps manage duplicates efficiently. The algorithm also relies on a result list to collect valid combinations and a recursion stack to explore candidate subsets.

What is the time complexity of Combination Sum II?

The typical backtracking solution has O(2^n) time complexity because each element can either be included or skipped during recursive exploration. Sorting the array adds O(n log n) preprocessing time but does not dominate the overall complexity. Space complexity is O(n) due to the recursion stack and temporary combination storage.

Combination Sum II solution and explanation

The problem

Approach overview

Approach 1: Backtracking Approach

Approach 2: Dynamic Programming Approach

Approach 3: Sorting + Pruning + Backtracking

Approach 4: Sorting + Pruning + Backtracking(Another Form)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Combination Sum II solution and explanation

The problem

Approach overview

Approach 1: Backtracking Approach

Approach 2: Dynamic Programming Approach

Approach 3: Sorting + Pruning + Backtracking

Approach 4: Sorting + Pruning + Backtracking(Another Form)

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems