Permutation and Combination: Candidate Sets in Backtracking

Example problem for this lesson: LeetCode 46 - Permutations (Medium)

Given a collection of distinct numbers, return all possible permutations. For example:

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

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

Back in Lesson 3, we covered the basic idea behind backtracking. Backtracking problems are solved recursively and can be connected to tree traversal — we can draw the decision path as a tree, and the backtracking process is simply traversing that tree.

However, in that article we only solved a very simple backtracking problem: the subset problem. In interviews, we need the ability to tackle more complex backtracking problems and handle various problem variants. In this article, we’ll use the classic permutation and combination problems as examples to discuss a key concept in solving backtracking problems: the candidate set.

This article will cover:

• The “what to choose” question in backtracking and candidate sets
• Backtracking solutions for full permutation, partial permutation, and combination problems
• How to maintain candidate sets in backtracking problems
• How to handle invalidated elements in backtracking problems

The Key Point of Backtracking: “What to Choose”

As we’ve discussed, backtracking is essentially the process of traversing a decision tree. So when solving a backtracking problem, the first thing to think about is the shape of all possible decision paths. For example, the decision tree for the subset problem looks like this:

The shape of the decision tree is mainly determined by the possible branches at each node — in other words, “what can we choose” and “what options are available” at each decision point.

For the subset problem, this “what to choose” question is very straightforward — there’s only one element to consider each time, and we either include it or not. However, for many other backtracking problems, the “what to choose” question isn’t so easy to answer. In these cases, we need to analyze the problem’s candidate set and how it changes, which gives us the approach to solve the problem.

Full Permutation: How to Maintain the Candidate Set

Let’s use the classic full permutation problem to explain the candidate set concept in backtracking.

In the full permutation problem, the number of branches in the decision tree isn’t fixed. We make $n$ decisions in total, where the $i$-th decision selects the $i$-th number in the permutation. When choosing the first number, all $n$ numbers are available. Since previously chosen numbers can’t be selected again, the number of available choices decreases as we go deeper. Taking $n=3$ as an example, the decision tree looks like this:

Thinking from the perspective of candidate sets: when making the first choice, all 3 numbers are available, so the candidate set has size 3. At the second choice, the candidate set shrinks to size 2; at the third choice, only one element remains. As you can see, the pattern of how the candidate set changes in the full permutation problem is: with each choice made, the candidate set loses one element, until it’s empty. We can annotate each node in the decision tree above with the candidate set elements, which makes things clearer.

As you can see, the selected set and the candidate set are complements of each other — together they make up all the elements. During the process of making and undoing choices in backtracking, the selected set and candidate set grow and shrink inversely.

How do we turn this idea into code? We could certainly use a data structure like HashSet to represent the candidate set. But if you go that route, you’ll find the code becomes rather verbose, and the “iterate-then-delete” operation on a set is awkward to write. I won’t show code using a set structure here. The key takeaway is: in general, an array is sufficient to represent the candidate set. The operations needed on the candidate set aren’t that many, and using an array is both simple and efficient.

In the subset problem, we defined a variable k representing which element we’re currently making a decision about. In fact, k serves as the boundary of the candidate set — elements after pointer k are candidates, while those before k are invalid and can no longer be chosen.

After each decision, incrementing k by one effectively removes the $k$-th element from the candidate set.

In the full permutation problem, the situation is trickier. At each decision point, any element in the candidate set can be chosen, which means we might need to remove an element from the middle of the candidate set, leaving a “hole” in the array. How do we handle this? We can use a clever technique: first swap the element to be removed with the $k$-th element, then increment k by one. The process is shown in the animation below:

Did you notice that in the figure above, the elements outside the candidate set are shown in blue? These are actually the selected set. As we analyzed earlier, the selected set and candidate set are complementary. If we view the blue portion as the selected set, then the element removed from the candidate set is exactly the one added to the selected set. In other words, we can use a single array to represent both the selected set and the candidate set simultaneously!

Once you understand the relationship illustrated in the figure, the solution code practically writes itself. We just need a single current array, where the left half represents selected elements and the right half represents candidate elements. The pointer k is both the starting position of candidate elements and the ending position of selected elements. This gives us a very concise solution:

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++) {
        // Choose number current[i]
        Collections.swap(current, k, i);
        // Increment k
        backtrack(current, k+1, res);
        // Undo the choice
        Collections.swap(current, k, i);
    }
}

Pay attention to the comment above the recursive function. When writing backtracking code, you need to be clear at all times about what constitutes the selected set and what constitutes the candidate set. The condition in the comment is called an “invariant.” On one hand, we can refer to the meaning of variable k within the function; on the other hand, when making recursive calls, we must ensure this condition always holds. Note especially that the recursive call passes k+1 — meaning we remove one candidate element — rather than i+1.

Partial Permutation: Choosing k from n

The full permutation problem is a permutation of choosing $n$ from $n$, denoted $P(n, n)$. In interviews, we’re likely to encounter various variants, so we should also master $P(n, k)$ (partial permutation) and $C(n, k)$ (combination).

The $P(n, k)$ problem is very straightforward — we just need to return the result after making the $k$-th decision, based on the full permutation approach. In other words, we only traverse the first $k$ levels of the decision tree. For example, when $n=3, k=2$, at level 2 of the decision tree, the selected set contains two elements, and we return those results.

The solution code is shown below — we only need to modify the recursion termination condition.

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

// current[0..m) is the selected set, current[m..N) is the candidate set
void backtrack(int k, List<Integer> current, int m, List<List<Integer>> res) {
    // When the selected set reaches k elements, collect the result and stop
    if (m == k) {
        res.add(new ArrayList<>(current.subList(0, k)));
        return;
    }
    // Choose from the candidate set
    for (int i = m; i < current.size(); i++) {
        // Choose number current[i]
        Collections.swap(current, m, i);
        backtrack(k, current, m+1, res);
        // Undo the choice
        Collections.swap(current, m, i);
    }
}

Note that $k$ is now part of the problem input, so the variable previously named k in our code has been renamed to m. Additionally, the if condition at the beginning of the recursive function has changed — when the selected set reaches $k$ elements, we collect the result and stop recursing.

Combination: Invalidated Elements

Due to the close relationship between permutations and combinations, the combination problem $C(n, k)$ — choosing $k$ from $n$ — can be derived with minor modifications to the $P(n, k)$ solution.

Let’s first think about the relationship between combinations and permutations. Two results with the same elements but different orderings are considered different permutations — for example, $[1, 2, 3]$ and $[2, 1, 3]$. But results that differ only in order are considered the same combination. So, if we only consider the ascending results from $P(n, k)$, we naturally eliminate duplicates and obtain $C(n, k)$.

How do we make the backtracking generate only ascending permutations? This requires a bit of thought, but it’s not too difficult. We just need to: whenever we choose a number $x$, remove all elements smaller than $x$ from the candidate set, so they’re no longer candidates.

If you think about it more carefully, the swap operation used in the permutation problem to maintain the candidate set is no longer needed here. For example, in the illustration below, after choosing element 6, to keep the result in ascending order, the preceding elements 4 and 5 must also be discarded. However, we don’t need to worry about the invalidated elements — we only need to track how the candidate set changes. We find that the remaining candidate set is still a contiguous segment of the array, with no “holes” like in the permutation problem. A single pointer is enough to represent the new candidate set.

The figure below shows the decision tree for $C(n, k)$. As you can see, the candidate sets are always contiguous. It doesn’t matter that the selected set isn’t contiguous — we can use a separate array to store the selected elements.

Following this approach, we can write the code for $C(n, k)$.

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
    if (current.size() == k) {
        res.add(new ArrayList<>(current));
        return;
    }
    // Choose from the candidate set
    for (int i = m; i < nums.size(); i++) {
        // Choose number nums[i]
        current.addLast(nums.get(i));
        // Elements nums[m..i) are invalidated
        backtrack(k, nums, i+1, current, res);
        // Undo the choice
        current.removeLast();
    }
}

Since the selected set and candidate set are no longer complementary, we use a separate array to store selected elements — similar to the subset problem.

The Relationship Between Combination and Subset Problems

Perhaps because permutation & combination feel like such a natural pair, we tend to approach the combination problem by adapting the permutation solution. In reality, the combination problem is closely related to the subset problem.

Solving Combinations via the Subset Problem

The combination problem can be viewed as a special case of the subset problem. Choosing $k$ numbers from $n$ is essentially finding all subsets of size $k$ from $n$ elements. In other words, the results of the combination problem are a subset of the subset problem’s results. By taking the subset problem’s decision tree and stopping recursion when the selected set reaches size $k$, we get the decision tree for the combination problem.

I won’t show the specific code here — I’ll leave it as an exercise for you to modify the subset problem’s solution code to obtain the $C(n, k)$ code.

Solving Subsets via the Combination Problem

For the subset problem, a set of size $n$ has $2^n$ possible subsets. For the combination problem $C(n,k)$, the number of results is the binomial coefficient $C_n^k$, also written as $\left( \! \begin{array}{c} n \\ r \end{array} \! \right)$. By the binomial theorem:

$$2^n = C_n^0 + C_n^1 + \dots + C_n^n$$

To obtain all $2^n$ subsets, we can compute all combinations of choosing $0, 1, \dots, n$ from $n$, and then combine them. Following this idea, we can modify the combination solution slightly to solve the subset problem:

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

// current is the selected set, nums[m..N) is the candidate set
void backtrack(List<Integer> nums, int m, Deque<Integer> current, List<List<Integer>> res) {
    // Collect the result at every node of the decision tree
    res.add(new ArrayList<>(current));
    if (m == nums.size()) {
	    // When the candidate set is empty, stop recursing
        return;
    }
    // Choose from the candidate set
    for (int i = m; i < nums.size(); i++) {
        // Choose number nums[i]
        current.addLast(nums.get(i));
        // Elements nums[m..i) are invalidated
        backtrack(nums, i+1, current, res);
        // Undo the choice
        current.removeLast();
    }
}

As you can see, each decision adds one element to the selected set. When the recursion reaches level $k$, it computes all subsets of size $k$. However, this approach to the subset problem isn’t as intuitive as the original solution, so I still recommend the original approach.

Summary

Permutation and combination problems are very practical and representative examples of backtracking, and working through them helps you build a solid grasp of fundamental backtracking techniques. However, they don’t have exact counterparts on LeetCode. The example problem at the beginning of this article is the full permutation problem. For the combination problem, LeetCode only has a simplified version 77. Combinations, where the numbers are fixed to the integers 1 through n.

Permutation and combination problems demonstrate the importance of the candidate set concept for organizing your thinking when solving backtracking problems. In fact, the “make a choice” and “undo a choice” operations in backtracking are essentially removing an element from and adding it back to the candidate set. When writing code, remember to add comments above the recursive function that clearly state which part of the array is the candidate set.

There are also some variants of permutation and combination problems — for example, when the input contains duplicate elements, how to avoid duplicate results requires using decision tree pruning techniques. The next article will cover how to prune correctly in backtracking problems.