Permutation vs Combination: Order Is the Only Question That Matters

You're deep into a backtracking problem. You write a solution. It runs. It produces results. Way too many results. You're generating [1, 2, 3] and [3, 1, 2] as separate answers when the problem only wanted them counted once.

This is the permutation vs combination confusion, and it shows up in interviews at the worst possible time: when you're already mid-solution and the clock is running and your interviewer has that neutral face that reveals absolutely nothing.

One question separates permutations from combinations: does the order of your selection matter?

Everything else follows. The formulas, the complexity, the backtracking templates. One question decides it all.

Order Matters vs. Order Doesn't

Four people: Alice, Bob, Carol, Dave.

Scenario A. You're assigning them to a podium. First place, second place, third place. Alice winning first is a different outcome from Alice winning second. The order is baked into the result.

Scenario B. You're picking a 3-person committee. Alice, Bob, and Carol on the committee is identical to Carol, Bob, and Alice. Nobody has a rank. Nobody has a title. They either made the committee or they didn't.

Scenario A is a permutation. Scenario B is a combination.

The formulas follow directly:

P(n, k) = n! / (n - k)!
C(n, k) = n! / (k! * (n - k)!)

For P(4, 3): 4! / 1! = 24. Twenty-four ordered ways to fill the podium.

For C(4, 3): 4! / (3! * 1!) = 4. Four committees. Same people. Far fewer arrangements.

That k! in the denominator divides out all the orderings you don't care about. For any given k-element selection, there are exactly k! ways to rearrange those same elements. Combinations collapse all of them into one.

Combinations are permutations with the duplicate orderings thrown out. Which gives you C(n, k) = P(n, k) / k!. That identity is worth internalizing.

What Does the Problem Actually Mean?

When a problem says "how many ways to arrange," "number of sequences," "passwords," "codes," or "rankings," you're looking at permutations. Order is part of the answer.

When it says "how many subsets," "choose k elements from," "groups," "teams," or "committees," you're looking at combinations. Order is irrelevant.

Some problems are ambiguous on purpose. "How many ways can you distribute 3 books to 2 people" sounds like combinations, but if Person A getting books {1, 2} differs from getting books {1, 3}, you're counting a form of permutations in disguise.

Always ask: does swapping the order of my selections produce a different valid outcome? If yes, permutations. If no, combinations. That's the whole disambiguation test.

The Templates Are Almost Identical. Almost.

This is where candidates get tripped up. The two backtracking templates look nearly the same. The structural difference is one parameter, and it's the entire point.

Permutations of length k from n elements:

def permutations(nums, k):
    result = []
    used = [False] * len(nums)

    def backtrack(current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack(current)
            current.pop()
            used[i] = False

    backtrack([])
    return result

The used array is the whole mechanism. You can pick any unused element at each step, so [1, 2] and [2, 1] are both generated. They're different sequences. They both belong in the output.

Combinations of length k from n elements:

def combinations(nums, k):
    result = []

    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()

    backtrack(0, [])
    return result

That start parameter is the only meaningful difference between these two functions. Once you've moved past index i, you never go back. [1, 2] and [2, 1] collapse into a single result. You only move forward.

Wait, that's it? That's the whole thing.

Permutations iterate from 0 every time and track which elements are used. Combinations only move forward with a start index. One parameter separates them.

Here's what the recursion trees look like for [1, 2, 3] with k=2:

The permutation tree fans out every time. The combination tree prunes everything to the left of the current index. That visual gap is the start parameter in action.

The Complexity Gap Is Genuinely Alarming

This is where the distinction stops being abstract and starts being the reason your solution times out.

All permutations of n elements: There are n! of them. Generating each requires O(n) work to copy. Total time: O(n · n!).

At n = 10, that's 36 million operations. At n = 12, it's over 5 billion. At n = 20, you are no longer doing computer science. You are waiting for geological time to pass.

All combinations of size k from n elements: The count is C(n, k), which peaks around C(n, n/2). For all subsets (k from 0 to n), you get 2^n total. Each requires O(k) work. Total: O(k · C(n, k)), or O(n · 2^n) for all subsets.

Still exponential. But C(10, 5) = 252. P(10, 10) = 3,628,800. That difference is what separates "runs in a millisecond" from "runs until the heat death of the universe."

Space complexity for both: O(k) for the recursion stack depth, plus O(output size) for storing results. If you're counting rather than generating, you only pay for the stack.

See Backtracking Time Complexity for the full derivation, including how the copy cost at each leaf factors in.

The k! Identity Pulls Its Weight

C(n, k) × k! = P(n, k) is not just trivia. It shows up in real problems.

Suppose you want all permutations of a k-element subset. Generate all combinations of size k, then generate all k! orderings of each. Total: C(n, k) × k! = P(n, k). This decomposition is useful when a problem has two distinct layers: first select the group, then arrange the group. Counting each layer separately and multiplying is almost always cleaner than reasoning about the full permutation space directly.

Pascal's triangle identity C(n, k) = C(n-1, k-1) + C(n-1, k) is the foundation of many DP counting problems. Either the last element is included or it isn't. See Bitmask Subset Enumeration for how this extends when you represent combinations as bitmasks.

What About Repeated Elements?

The formulas above assume no repetition. Both have variants that come up in interviews.

Permutations with repetition: n^k. A 4-digit PIN using digits 0-9 gives 10^4 = 10,000 possibilities. You can reuse digits.

Combinations with repetition: C(n + k - 1, k). Less common, but it appears in "stars and bars" counting problems where you're distributing identical objects into distinct bins.

The backtracking templates adjust slightly. For permutations with repetition, remove the used check entirely. For combinations with repetition, pass i instead of i + 1 in the recursive call so the same element can be chosen again.

Four Problems, Two Templates

These four LeetCode problems cover the full space:

• LeetCode 46 (Permutations): generate all permutations of a distinct array. Direct application of the permutation template.
• LeetCode 77 (Combinations): generate all k-element combinations. Direct application of the combination template.
• LeetCode 78 (Subsets): generate all subsets. The combination template with k iterating from 0 to n.
• LeetCode 47 (Permutations II): permutations with duplicate elements. Sort first, then add a "skip duplicate at same level" guard.

Understanding both core templates makes all four feel like variations on one idea rather than four separate things to memorize. See Backtracking Algorithm for the full template with pruning strategies.

Stating Complexity Out Loud in an Interview

You'll often need to analyze complexity before writing code. The fast path:

1. Decide: does order matter? Permutation or combination.
2. State the count: P(n, k) = n!/(n-k)! or C(n, k) = n!/(k!(n-k)!).
3. Multiply by k for the copy cost at each leaf.
4. Check the constraints: is the total output size actually feasible?

If n = 20 and you're generating all permutations, n! is about 2.4 × 10^18. Not feasible. If you're generating combinations of size 3 from 20 elements, C(20, 3) = 1,140. Fine.

Distinguishing permutation space from combination space is how you know whether your approach is viable before you've written a single line. Same input, wildly different scale, one question to tell them apart.

SpaceComplexity includes backtracking problems where you practice this exact narration under timed conditions, with rubric-based feedback on whether your complexity reasoning lands at the strong-hire bar.

The Short Version

• One question: does swapping the order of your selection produce a different valid outcome? Yes means permutations. No means combinations.
• Formulas: P(n, k) = n!/(n-k)!, C(n, k) = n!/(k!(n-k)!). C is P divided by k! to remove duplicate orderings.
• Code: permutation templates track used elements and iterate from 0 every time; combination templates track a start index and only move forward.
• Complexity: P(n, n) = n! and escalates catastrophically. Combinations stay feasible for much larger inputs.
• Repetition: drop the used guard for permutations, pass i not i + 1 for combinations.

Further Reading

• Permutation (Wikipedia)
• Combination (Wikipedia)
• Combinatorics (Wikipedia)
• Stars and bars (Wikipedia)
• LeetCode Problem 46: Permutations