Revisiting Permutations and Combinations: Deduplication Strategies in Backtracking

Problems for this lesson (two in total):

Problem One, the subsets problem with duplicate elements: LeetCode 90 - Subsets II (Medium)

Given a collection of integers nums that might contain duplicates, return all possible subsets (the power set). For example:

• Input: nums = [1,2,3]
• Output:

[
 []
 [1],
 [2],
 [1,2],
 [2,2],
 [1,2,2],
]

Problem Two, the permutations problem with duplicate elements: LeetCode 47 - Permutations II (Medium)

Given a collection of integers that might contain duplicates, return all possible unique permutations. For example:

• Input: [1, 2, 2]
• Output:

[
  [1,1,2],
  [1,2,1],
  [2,1,1],
]

The subsets problem and the permutations problem are both classic backtracking problems, and we covered their detailed approaches and solutions in the previous article. The problems in this lesson are variations of those — both involve duplicate elements in the input, and we need to avoid producing duplicate results. This article assumes you are already familiar with the approaches and solutions for subset, permutation, and combination problems. If you are not yet clear on the solutions for these problems, I recommend reading the previous article first: LeetCode Problem Deep Dive | 08 Permutations and Combinations: Candidate Sets in Backtracking.

Both of these problems test pruning strategies in backtracking. Pruning essentially means removing certain branches from the decision tree so they are not explored. We need to think about how to eliminate duplicate results based on the nature of the problem, and how to implement deduplication as pruning on the decision tree.

This article will cover the deduplication strategies, pruning approaches, and solution code for the subsets, permutations, and combinations problems.

Subsets with Duplicate Elements

Let’s first review the decision tree for the subsets problem. Backtracking involves $n$ decisions in total, and each decision has two branches — whether or not to include the $i$-th element in the subset. Taking $[1, 2, 3]$ as an example, the decision tree looks like the figure below.

The solution code is as follows:

public List<List<Integer>> subsets(int[] nums) {
    Deque<Integer> current = new ArrayDeque<>(nums.length);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, current, res);
    return res;
}

// Candidate set: nums[k..N)
void backtrack(int[] nums, int k, Deque<Integer> current, List<List<Integer>> res) {
    if (k == nums.length) {
        res.add(new ArrayList<>(current));
        return;
    }

    // Do not select the k-th element
    backtrack(nums, k+1, current, res);

    // Select the k-th element
    current.addLast(nums[k]);
    backtrack(nums, k+1, current, res);
    current.removeLast();
}

So, when the input contains duplicate elements, how do we eliminate duplicate results? Let’s find the approach through a concrete example. Take the input $[1, 2, 2, 2]$ — $[1, 2, 2]$ is one of its subsets. To distinguish the duplicate $2$s, let’s label the three $2$s as $2_1$, $2_2$, and $2_3$. Then the subset $[1, 2, 2]$ could be $[1, 2_1, 2_2]$, $[1, 2_1, 2_3]$, or $[1, 2_2, 2_3]$. Among these three duplicate results, we only need to keep one.

We can establish a rule: in a consecutive sequence of $2$s, if the first $2$ is not included in the subset, then none of the subsequent $2$s can be included either. In other words, if we don’t select $2_1$, then we cannot select $2_2$ or $2_3$. This way, to have two $2$s in the result, the only possibility is $2_1$ and $2_2$. Deduplication achieved! The corresponding decision tree pruning is shown in the figure below.

How do we translate this pruning logic into code? Two things are needed:

1. Before backtracking, sort all elements in the array so that equal elements are adjacent;
2. Each time we decide on element $x$, if we choose not to select candidate element $x$, then we also skip all consecutive equal elements that follow $x$.

Here is the solution code. As you can see, the pruning logic is implemented by removing multiple elements from the candidate set at once. The concept of the candidate set also plays an important role in understanding “pruning.”

public List<List<Integer>> subsetsWithDup(int[] nums) {
    // Sort elements to ensure equal elements are adjacent
    Arrays.sort(nums);
    Deque<Integer> current = new ArrayDeque<>(nums.length);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(nums, 0, current, res);
    return res;
}

// Candidate set: nums[k..N)
void backtrack(int[] nums, int k, Deque<Integer> current, List<List<Integer>> res) {
    if (k == nums.length) {
        res.add(new ArrayList<>(current));
        return;
    }

    // Select nums[k]
    current.addLast(nums[k]);
    backtrack(nums, k+1, current, res);
    current.removeLast();

    // Do not select nums[k]
    // Remove all subsequent elements equal to nums[k], i.e., nums[k..j), from the candidate set
    int j = k;
    while (j < nums.length && nums[j] == nums[k]) {
        j++;
    }
    backtrack(nums, j, current, res);
}

Permutations with Duplicate Elements

The permutations problem with duplicate elements follows a very similar idea to the subsets problem, except that due to the different backtracking approach, the code looks somewhat different. Let’s first review the original code for the permutations problem:

public List<List<Integer>> permute(List<Integer> nums) {
    List<Integer> current = new ArrayList<>(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(current, 0, res);
    return res;
}

// current[0..k) is the selected set, current[k..N) is the candidate set
void backtrack(List<Integer> current, int k, List<List<Integer>> res) {
    if (k == current.size()) {
        res.add(new ArrayList<>(current));
        return;
    }
    // Choose from the candidate set
    for (int i = k; i < current.size(); i++) {
        // Select number current[i]
        Collections.swap(current, k, i);
        // Increment k
        backtrack(current, k+1, res);
        // Undo the selection
        Collections.swap(current, k, i);
    }
}

For the permutations problem with duplicate elements, let’s again think about the pruning strategy using the input $[1, 2, 2, 2]$: label the three $2$s as $2_1$, $2_2$, and $2_3$. For the permutation $[1, 2, 2, 2]$, it could actually be $[1, 2_1, 2_2, 2_3]$, $[1, 2_1, 2_3, 2_2]$, $[1, 2_2, 2_1, 2_3]$, $[1, 2_2, 2_3, 2_1]$, $[1, 2_3, 2_1, 2_2]$, or $[1, 2_3, 2_2, 2_1]$ — 6 possibilities in total. How should we prune to keep only one of these results?

We can establish a rule: if there are multiple candidate $2$s, we can only select the first $2$; the remaining $2$s cannot be selected this time. In other words, the three $2$s must be selected in order — first $2_1$, then $2_2$, and finally $2_3$ — so that only the arrangement $2_1, 2_2, 2_3$ is a valid result. Deduplication achieved! The corresponding decision tree pruning is shown in the figure below.

However, for the permutations problem, we cannot guarantee that equal elements remain adjacent simply by sorting the original array. During backtracking, various swap operations break the original adjacency relationships. So we need to use a set to help determine whether a candidate element has appeared before.

Here is the solution code. As you can see, the pruning logic is implemented by skipping certain elements in the candidate set.

public List<List<Integer>> permuteUnique(List<Integer> nums) {
    List<Integer> current = new ArrayList<>(nums);
    List<List<Integer>> res = new ArrayList<>();
    backtrack(current, 0, res);
    return res;
}

// Selected set current[0..m), candidate set current[m..N)
void backtrack(List<Integer> current, int m, List<List<Integer>> res) {
    if (m == current.size()) {
        res.add(new ArrayList<>(current));
        return;
    }

    // Use a set to check whether an equal candidate element has already appeared.
    Set<Integer> seen = new HashSet<>();
    for (int i = m; i < current.size(); i++) {
        int e = current.get(i);
        if (seen.contains(e)) {
            // If an equal element has already appeared, skip this element
            continue;
        }
        seen.add(e);
        Collections.swap(current, m, i);
        backtrack(current, m+1, res);
        Collections.swap(current, m, i);
    }
}

Combinations with Duplicate Elements

The combinations problem doesn’t have a direct corresponding problem on LeetCode, but for the sake of completeness, let’s continue our discussion after subsets and permutations and think about how to solve the combinations problem with duplicate elements. As before, let’s first review the solution code for the combinations problem:

public List<List<Integer>> combine(List<Integer> nums, int k) {
    Deque<Integer> current = new ArrayDeque<>();
    List<List<Integer>> res = new ArrayList<>();
    backtrack(k, nums, 0, current, res);
    return res;
}

// current is the selected set, nums[m..N) is the candidate set
void backtrack(int k, List<Integer> nums, int m, Deque<Integer> current, List<List<Integer>> res) {
    // When the selected set reaches k elements, collect the result and stop selecting
    if (current.size() == k) {
        res.add(new ArrayList<>(current));
        return;
    }
    // Choose from the candidate set
    for (int i = m; i < nums.size(); i++) {
        // Select number nums[i]
        current.addLast(nums.get(i));
        // Elements nums[m..i) are invalidated
        backtrack(k, nums, i+1, current, res);
        // Undo the selection
        current.removeLast();
    }
}

In fact, the deduplication approach we discussed for the permutations problem can be directly applied to the combinations problem. Their pruning strategies are exactly the same!

Taking the input $[1, 2, 2, 2]$ as an example, following the same approach as the permutations problem, we establish the rule: if there are multiple candidate $2$s, we can only select the first $2$; the remaining $2$s cannot be selected this time. In other words, if the result contains only one $2$, it can only be $2_1$; if the result contains two $2$s, they can only be $2_1$ and $2_2$.

When translating this approach into code, the combinations problem is actually much simpler than the permutations problem. This is because the combinations problem doesn’t involve swap operations that disrupt element ordering. We just need to sort the array at the beginning, and then we can easily determine whether an element is the first among its equal peers. The solution code is as follows:

public List<List<Integer>> combine(int[] nums, int k) {
    // Sort elements to ensure equal elements are adjacent
    Arrays.sort(nums);
    Deque<Integer> current = new ArrayDeque<>();
    List<List<Integer>> res = new ArrayList<>();
    backtrack(k, nums, 0, current, res);
    return res;
}

// current is the selected set, nums[m..N) is the candidate set
void backtrack(int k, int[] nums, int m, Deque<Integer> current, List<List<Integer>> res) {
    // When the selected set reaches k elements, collect the result and stop selecting
    if (current.size() == k) {
        res.add(new ArrayList<>(current));
        return;
    }
    // Choose from the candidate set
    for (int i = m; i < nums.length; i++) {
        if (i > m && nums[i] == nums[i-1]) {
            // nums[i] equals the previous element, meaning it's not the first occurrence among equals — skip it.
            continue;
        }
        // Select number nums[i]
        current.addLast(nums[i]);
        // Elements nums[m..i) are invalidated
        backtrack(k, nums, i+1, current, res);
        // Undo the selection
        current.removeLast();
    }
}

Summary

In a single article, we’ve covered the duplicate-element versions of the subsets, permutations, and combinations problems. As you can see, their approaches are all very similar. To summarize, this category of backtracking problems requiring deduplication can all follow these steps:

1. First, write the duplicate-free version of the problem correctly (this is important!);
2. Think about the pruning strategy — typically removing or skipping certain elements in the candidate set;
3. Based on the characteristics of the code, add specific pruning checks, either using pre-sorting or leveraging data structures.

The solution code for this lesson’s problems may look simple, but it still takes practice to become proficient. The difficulty of backtracking problems lies not only in the problem-solving approach but also in writing clear, understandable, bug-free code. Practice often and refine your code — that’s the key to mastering backtracking problems.