Backtracking for Coding Interviews: Combination vs Permutation (with Top Problems)

Backtracking is one of the most important patterns for coding interviews. Many problems on platforms like LeetCode revolve around generating combinations, permutations, subsets, and solving constraint problems.

Understanding when to use combinations vs permutations is the key to solving these problems quickly.

---

1. Combination vs Permutation

Before writing code, the first question you should ask is:

Does order matter?

Combination

In combinations:

Order does NOT matter

Example:

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

Both represent the same combination.

Mathematical Formula

Code Logic

We avoid duplicates by moving the index forward.

void combination(int start, List<Integer> path){

    result.add(new ArrayList<>(path));

    for(int i=start;i<n;i++){

        path.add(nums[i]);

        combination(i+1,path);

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

Key Logic

Next recursion → i + 1

Because previous elements should not be reused before the current index.

---

Permutation

In permutations:

Order matters

Example:

[1,2] ≠ [2,1]

Both are different permutations.

Mathematical Formula

Code Logic

We must track which elements are already used.

void permutation(List<Integer> path, boolean[] used){

    if(path.size()==n){
        result.add(new ArrayList<>(path));
        return;
    }

    for(int i=0;i<n;i++){

        if(used[i]) continue;

        used[i]=true;
        path.add(nums[i]);

        permutation(path,used);

        path.remove(path.size()-1);
        used[i]=false;
    }
}

Key Logic

Loop from 0 → n
Track visited elements

---

Quick Comparison

Feature	Combination	Permutation
Order matters	No	Yes
Index movement	i+1	always 0→n
Visited array	Not needed	Needed
Duplicates avoided	index movement	visited array

---

2. Core Backtracking Principle

Every backtracking solution follows this pattern:

choose
explore
unchoose

Code structure:

path.add(x);

dfs(...);

path.remove(path.size()-1);

---

3. Most Important Backtracking Patterns

Backtracking problems can usually be classified into 5 templates.

---

Pattern 1: Subsets (Pick / Not Pick)

Used when every element has two choices.

include
exclude

Template:

void dfs(int i,List<Integer> path){

    if(i==n){
        ans.add(new ArrayList<>(path));
        return;
    }

    path.add(nums[i]);
    dfs(i+1,path);

    path.remove(path.size()-1);

    dfs(i+1,path);
}

Top problems:

• Subsets
• Subsets II

---

Pattern 2: Combination

Used when selecting elements without caring about order.

Template:

for(int i=start;i<n;i++){

    path.add(nums[i]);

    dfs(i+1,path);

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

Top problems:

• Combinations
• Combination Sum
• Combination Sum II

---

Pattern 3: Permutations

Used when order matters.

Template:

for(int i=0;i<n;i++){

    if(used[i]) continue;

    used[i]=true;

    path.add(nums[i]);

    dfs(path,used);

    path.remove(path.size()-1);

    used[i]=false;
}

Top problems:

• Permutations
• Permutations II

---

Pattern 4: Combination Sum (Reuse Allowed)

Some problems allow reusing elements multiple times.

Template:

path.add(nums[i]);

dfs(i,target-nums[i],path);

path.remove(path.size()-1);

dfs(i+1,target,path);

Top problems:

• Combination Sum
• Combination Sum III

---

Pattern 5: Constraint Placement

Used in grid or board problems.

Examples include:

• N-Queens
• Sudoku Solver
• Word Search

Template:

for(each possible choice){

    if(valid){

        place choice

        dfs()

        remove choice
    }
}

---

4. Most Asked Backtracking Problems (Interview List)

These appear frequently in FAANG and product-based interviews.

Easy

• Subsets
• Permutations

Medium

• Combination Sum
• Letter Combinations of a Phone Number
• Palindrome Partitioning

Hard

• N-Queens
• Sudoku Solver

---

5. Complexity of Backtracking

Most backtracking algorithms are exponential.

Typical complexity:

O(2^n)
O(n!)

Examples:

Subsets → 2^n
Permutations → n!

---

Final Mental Model

When solving a recursion problem, ask these three questions:

1. Does order matter?
2. Can elements repeat?
3. Are there constraints?

Mapping:

Order matters → Permutation
Order doesn't matter → Combination
Reuse allowed → Combination Sum
Grid constraint → Placement

---