Jaspreet singh

Posted on Jun 17

Combination Sum II | Backtracking

#algorithms #computerscience #java #leetcode

Problem Statement

Given a collection of candidate numbers candidates and a target number target, find all unique combinations where the chosen numbers sum to the target.

Each number may be used at most once.

The solution set must not contain duplicate combinations.

Brute Force Intuition

Generate all possible subsets and check:

Does subset sum == target ?

Store valid subsets in a Set to remove duplicates.

This works but generates many duplicate combinations unnecessarily.

Complexity

Time Complexity: O(2ᴺ × N)
Space Complexity: O(2ᴺ)

Moving Towards the Optimal Approach

Notice:

candidates = [1,1,2]
target = 3

Without handling duplicates:

First 1 + 2 => [1,2]

Second 1 + 2 => [1,2]

Duplicate answer generated.

Instead of removing duplicates later, we can prevent them from being created.

Pattern Recognition

Whenever you see:

Generate all combinations
Duplicates present
Unique answers required

Think:

Sort + Backtracking + Skip Duplicates

Key Observations

1. Sort the Array

Arrays.sort(candidates);

After sorting:

[1,1,2,5,6,7,10]

Duplicates become adjacent.

2. Skip Duplicate Choices

if(i > index && candidates[i] == candidates[i - 1])
    continue;

Meaning:

At the same recursion level, only consider the first occurrence.

3. Use Element Only Once

After picking:

helper(i + 1, ...)

not

helper(i, ...)

because reuse is not allowed.

Optimal Java Solution

import java.util.*;

class Solution {

    public List<List<Integer>> combinationSum2(int[] candidates,
                                               int target) {

        Arrays.sort(candidates);

        List<List<Integer>> ans = new ArrayList<>();

        helper(0,
               candidates,
               target,
               new ArrayList<>(),
               ans);

        return ans;
    }

    private void helper(int index,
                        int[] candidates,
                        int target,
                        List<Integer> ds,
                        List<List<Integer>> ans) {

        if (target == 0) {
            ans.add(new ArrayList<>(ds));
            return;
        }

        for (int i = index; i < candidates.length; i++) {

            if (i > index &&
                candidates[i] == candidates[i - 1]) {
                continue;
            }

            if (candidates[i] > target) {
                break;
            }

            ds.add(candidates[i]);

            helper(i + 1,
                   candidates,
                   target - candidates[i],
                   ds,
                   ans);

            ds.remove(ds.size() - 1);
        }
    }
}

Dry Run

Input

candidates = [10,1,2,7,6,1,5]
target = 8

After Sorting:

[1,1,2,5,6,7,10]

Valid Combinations

[1,1,6]
[1,2,5]
[1,7]
[2,6]

Why Skip Duplicates?

Suppose:

index = 0

1 1 2
↑ ↑

If we start a combination using both 1s separately at the same level:

[1,2]
[1,2]

duplicate answers appear.

Hence:

if(i > index && nums[i] == nums[i - 1])
    continue;

Complexity Analysis

Metric	Complexity
Time Complexity	O(2ᴺ)
Space Complexity	O(N)

Recursion depth is at most N.

Interview One-Liner

Sort the array, use backtracking to generate combinations, move to the next index after picking an element, and skip duplicate elements at the same recursion level.

Pattern Learned

Combination Sum I
=
Unlimited Reuse
=
Stay at Same Index

Combination Sum II
=
Use Once
+
Duplicates Present
=
Move Forward
+
Skip Duplicates

DEV Community