AdvancedBacktracking

Backtracking without duplicate answers

Sort first, then at each level skip a number equal to the one just tried. Duplicates never get generated in the first place.

The idea

With repeated numbers, the plain template produces the same combination several times. Removing duplicates afterwards is slow and wasteful. Prevent them instead.

Sort the input so equal numbers sit together. At one level of the recursion, if nums[i] equals nums[i − 1] and i isn't the first choice at this level, skip it: that branch was already explored.

Worked example

Combination Sum II: candidates [1, 1, 2], target 3

sorted [1, 1, 2]
first level: pick 1 (index 0) → then 2 → [1, 2] ✓
first level: index 1 is also 1 → skip, or [1, 2] would appear twice

In code (Python)

def combination_sum2(candidates, target):
    candidates.sort()
    result, path = [], []

    def explore(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i - 1]:
                continue                 # same value at this level
            if candidates[i] > remaining:
                break                    # sorted: nothing later fits
            path.append(candidates[i])
            explore(i + 1, remaining - candidates[i])
            path.pop()

    explore(0, target)
    return result

Exponential in the worst case; pruning makes it much faster in practice.

How to spot it

“unique combinations / subsets / permutations” and the input has repeated values.

Common mistakes

Skipping with `i > 0` instead of `i > start`, which also removes valid answers.
Forgetting to sort first.

Practise it

Go further

Up next for you · Beginner

“Have I seen this?” is a set →

All tips