Scale Engineer

Combination Sum II

Med
#0040Time: O(N log N + 2^N * N). Sorting takes O(N log N). The backtracking can explore up to 2^N subsets. For each valid combination, we create a copy of the list (taking up to O(N) time) and add it to a hash set (average O(N) time for list hashing). This leads to a rough upper bound of O(2^N * N).Space: O(N + K * L), where N is the number of candidates, K is the number of unique combinations, and L is the average length of a combination. This includes O(N) for the recursion stack and temporary list, and O(K * L) for the hash set storing the results.12 companies
Patterns
Backtracking
Data structures
Array
Companies
AdobeAmazonBloombergByteDance

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach uses a standard backtracking algorithm to find all possible combinations that sum up to the target. To handle duplicate combinations that may arise from duplicate numbers in the input array, it stores the valid combinations in a HashSet. This automatically filters out duplicates. The input array is sorted first to ensure that combinations like [1, 7] and [7, 1] are not generated as distinct; only the sorted version [1, 7] is considered.

Algorithm

  • Sort the candidates array.
  • Initialize a HashSet<List<Integer>> to store unique combinations.
  • Define a recursive function findCombinations(index, target, currentList, resultSet).
  • In the recursive function:
    • If target is 0, add a copy of currentList to resultSet and return.
    • If target is negative or index is out of bounds, return.
    • Loop from index to the end of candidates:
      • Add candidates[i] to currentList.
      • Recursively call findCombinations(i + 1, target - candidates[i], ...).
      • Remove the last element from currentList (backtrack).
  • Call the initial recursive function with index=0, target, an empty list, and the resultSet.
  • Convert the resultSet to a List and return it.

Walkthrough

Start with sorting the candidates array. This helps in two ways: it groups duplicate numbers together and it helps in generating combinations in a canonical order, which is a prerequisite for using a Set of lists effectively. Define a recursive helper function, say findCombinations(index, target, currentList, resultSet). The base cases for the recursion are:

  • If target == 0, a valid combination is found. Add a copy of currentList to the resultSet.
  • If target < 0 or index is out of bounds, stop this path. In the recursive step, iterate from the current index to the end of the candidates array. For each element candidates[i], make a recursive call:
  • Add candidates[i] to currentList.
  • Call findCombinations(i + 1, target - candidates[i], currentList, resultSet). We use i + 1 to ensure each element is used at most once.
  • Backtrack by removing candidates[i] from currentList. The main function initializes an empty HashSet<List<Integer>>, calls the recursive helper, and finally converts the set to a list to return the result. The use of a Set simplifies the logic for handling duplicates, as we don't need to add special checks within the recursion to avoid them. However, this comes at the cost of performance overhead from hash computations and storing potentially many redundant paths before filtering.
import java.util.*; class Solution {    public List<List<Integer>> combinationSum2(int[] candidates, int target) {        Set<List<Integer>> resultSet = new HashSet<>();        Arrays.sort(candidates); // Sorting is important for the Set to work correctly on lists        findCombinations(candidates, 0, target, new ArrayList<>(), resultSet);        return new ArrayList<>(resultSet);    }     private void findCombinations(int[] candidates, int index, int target, List<Integer> current, Set<List<Integer>> resultSet) {        if (target == 0) {            resultSet.add(new ArrayList<>(current));            return;        }        if (target < 0) {            return;        }         for (int i = index; i < candidates.length; i++) {            current.add(candidates[i]);            // Move to the next index 'i + 1' since each number can be used only once            findCombinations(candidates, i + 1, target - candidates[i], current, resultSet);            current.remove(current.size() - 1); // Backtrack        }    }}

Complexity

Time

O(N log N + 2^N * N). Sorting takes O(N log N). The backtracking can explore up to 2^N subsets. For each valid combination, we create a copy of the list (taking up to O(N) time) and add it to a hash set (average O(N) time for list hashing). This leads to a rough upper bound of O(2^N * N).

Space

O(N + K * L), where N is the number of candidates, K is the number of unique combinations, and L is the average length of a combination. This includes O(N) for the recursion stack and temporary list, and O(K * L) for the hash set storing the results.

Trade-offs

Pros

  • Relatively simple to implement as the logic for handling duplicates is offloaded to the HashSet.

  • Correctly solves the problem.

Cons

  • Less efficient due to generating many duplicate combinations that are later discarded.

  • The use of a HashSet for lists can have performance overhead due to hashing the entire list content.

Solutions

public class Solution {    private List < IList < int >> ans = new List < IList < int >> ();    private List < int > t = new List < int > ();    private int[] candidates;    public IList < IList < int >> CombinationSum2(int[] candidates, int target) {        Array.Sort(candidates);        this.candidates = candidates;        dfs(0, target);        return ans;    }    private void dfs(int i, int s) {        if (s == 0) {            ans.Add(new List < int > (t));            return;        }        if (i >= candidates.Length || s < candidates[i]) {            return;        }        for (int j = i; j < candidates.Length; ++j) {            if (j > i && candidates[j] == candidates[j - 1]) {                continue;            }            t.Add(candidates[j]);            dfs(j + 1, s - candidates[j]);            t.RemoveAt(t.Count - 1);        }    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem