Course4all
Join us on telegram
Home/dsa/Backtracking/Combinations

Combinations

Master this topic with zero to advance depth.

Combinations

Choosing K from N

This is a classic nCrnCr problem. The goal is to choose KK elements from the set {1,2,...,N}\{1, 2, ..., N\}. Unlike permutations, the order doesn't matter.

Efficient Search

To avoid duplicate combinations like [1, 2] and [2, 1], we always choose numbers in increasing order. This means after choosing ii, the next number must be from {i+1,...,N}\{i+1, ..., N\}.

Pruning Optimization

If the number of remaining elements in the set is less than the number of elements we still need to pick, we can backtrack early.

Choose K numbers from 1 to N. Includes visual increasing-order tree.

Medium

Examples

Input: n = 4, k = 2
Output: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]
Approach 1

Level I: Recursive Backtracking (Include/Exclude)

Intuition

For each number from 1 to NN, we either include it in our current combination or skip it.

At index ii, we either add ii to our list and call dfs(i + 1, count + 1), or we don't add ii and call dfs(i + 1, count). If count == k, we found a solution.

⏱ O(k * C(N, k))💾 O(k) for recursion stack.

Detailed Dry Run

Dry Run: n=3, k=2 | Start | Path | Action | Next State | | :---- | :--- | :----------------- | :--------- | | 1 | [] | Choose 1, dfs(2) | [1] | | 2 | [1] | Choose 2, RES:[1,2]| - | | 2 | [1] | Backtrack, try 3 | [1,3] | | 3 | [1] | Choose 3, RES:[1,3]| - | | 1 | [] | Skip 1, try Choose 2| [2] |
java
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, int n, int k, List<Integer> current, List<List<Integer>> res) {
        if (current.size() == k) {
            res.add(new ArrayList<>(current));
            return;
        }
        if (start > n) return;
        
        // Include
        current.add(start);
        backtrack(start + 1, n, k, current, res);
        current.remove(current.size() - 1);
        
        // Exclude
        backtrack(start + 1, n, k, current, res);
    }
}
Approach 2

Level II: Optimized Backtracking (Loop-based Pruning)

Intuition

Instead of binary choice, use a loop to pick the next element. Only iterate through elements that could possibly complete a combination of size KK.

The current number ii can go up to N−(K−current.size())+1N - (K - current.size()) + 1. Beyond that, there aren't enough numbers left to reach size KK.

⏱ O(k * C(N, k))💾 O(k)

Detailed Dry Run

n=4, k=3

  1. At root, i can only go up to 4−3+1=24 - 3 + 1 = 2. So we only try picking 1 or 2 as the first element.
java
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>(), res);
        return res;
    }
    private void backtrack(int start, int n, int k, List<Integer> current, List<List<Integer>> res) {
        if (current.size() == k) {
            res.add(new ArrayList<>(current));
            return;
        }
        // Pruning: i <= n - (k - current.size()) + 1
        for (int i = start; i <= n - (k - current.size()) + 1; i++) {
            current.add(i);
            backtrack(i + 1, n, k, current, res);
            current.remove(current.size() - 1);
        }
    }
}
← Previous QuestionN-Queens
Next Question →Sudoku Solver