77. Combinations - Explanation

Description

You are given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example 1:

Input: n = 3, k = 2

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

Example 2:

Input: n = 3, k = 3

Output: [[1,2,3]]

Constraints:

1 <= k <= n <= 20

Topics

Backtracking

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Recursion - Understanding how to break problems into smaller subproblems with base cases
Backtracking - Making choices (include/exclude), exploring paths, and undoing choices
Bit Manipulation - Using bitmasks to represent subsets (for the bit manipulation approach)
Combinatorics Basics - Understanding what combinations are and how they differ from permutations

1. Backtracking - I

Intuition

To generate all combinations of k numbers from 1 to n, we make a binary choice for each number: include it or exclude it. This forms a decision tree where each path represents a subset. We only keep subsets of exactly size k.

Algorithm

Start with an empty combination and index i = 1.
At each step, we have two choices: include the current number i in the combination, or skip it.
Recursively process both choices by incrementing i.
When i exceeds n, check if the combination has exactly k elements. If so, add a copy to the result.
Backtrack by removing the added element before exploring the skip branch.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def backtrack(i, comb):
            if i > n:
                if len(comb) == k:
                    res.append(comb.copy())
                return

            comb.append(i)
            backtrack(i + 1, comb)
            comb.pop()
            backtrack(i + 1, comb)

        backtrack(1, [])
        return res

public class Solution {
    private List<List<Integer>> res;

    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>());
        return res;
    }

    private void backtrack(int i, int n, int k, List<Integer> comb) {
        if (i > n) {
            if (comb.size() == k) {
                res.add(new ArrayList<>(comb));
            }
            return;
        }

        comb.add(i);
        backtrack(i + 1, n, k, comb);
        comb.remove(comb.size() - 1);
        backtrack(i + 1, n, k, comb);
    }
}

class Solution {
    vector<vector<int>> res;
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> comb;
        backtrack(1, n, k, comb);
        return res;
    }

private:
    void backtrack(int i, int n, int k, vector<int>& comb) {
        if (i > n) {
            if (comb.size() == k) {
                res.push_back(comb);
            }
            return;
        }

        comb.push_back(i);
        backtrack(i + 1, n, k, comb);
        comb.pop_back();
        backtrack(i + 1, n, k, comb);
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number[][]}
     */
    combine(n, k) {
        const res = [];

        const backtrack = (i, comb) => {
            if (i > n) {
                if (comb.length === k) {
                    res.push([...comb]);
                }
                return;
            }

            comb.push(i);
            backtrack(i + 1, comb);
            comb.pop();
            backtrack(i + 1, comb);
        };

        backtrack(1, []);
        return res;
    }
}

public class Solution {
    public List<List<int>> Combine(int n, int k) {
        List<List<int>> res = new List<List<int>>();

        void Backtrack(int i, List<int> comb) {
            if (i > n) {
                if (comb.Count == k) {
                    res.Add(new List<int>(comb));
                }
                return;
            }

            comb.Add(i);
            Backtrack(i + 1, comb);
            comb.RemoveAt(comb.Count - 1);
            Backtrack(i + 1, comb);
        }

        Backtrack(1, new List<int>());
        return res;
    }
}

func combine(n int, k int) [][]int {
    res := [][]int{}

    var backtrack func(i int, comb []int)
    backtrack = func(i int, comb []int) {
        if i > n {
            if len(comb) == k {
                temp := make([]int, len(comb))
                copy(temp, comb)
                res = append(res, temp)
            }
            return
        }

        comb = append(comb, i)
        backtrack(i+1, comb)
        comb = comb[:len(comb)-1]
        backtrack(i+1, comb)
    }

    backtrack(1, []int{})
    return res
}

class Solution {
    fun combine(n: Int, k: Int): List<List<Int>> {
        val res = mutableListOf<List<Int>>()

        fun backtrack(i: Int, comb: MutableList<Int>) {
            if (i > n) {
                if (comb.size == k) {
                    res.add(ArrayList(comb))
                }
                return
            }

            comb.add(i)
            backtrack(i + 1, comb)
            comb.removeAt(comb.size - 1)
            backtrack(i + 1, comb)
        }

        backtrack(1, mutableListOf())
        return res
    }
}

class Solution {
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        var res = [[Int]]()

        func backtrack(_ i: Int, _ comb: inout [Int]) {
            if i > n {
                if comb.count == k {
                    res.append(comb)
                }
                return
            }

            comb.append(i)
            backtrack(i + 1, &comb)
            comb.removeLast()
            backtrack(i + 1, &comb)
        }

        var comb = [Int]()
        backtrack(1, &comb)
        return res
    }
}

Time & Space Complexity

Time complexity: $O(k * \frac {n!}{(n - k)! * k!})$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

2. Backtracking - II

Intuition

Instead of making include/exclude decisions, we iterate through available numbers and always include one. Starting from a given position ensures we never revisit smaller numbers, avoiding duplicates. We stop when the combination reaches size k.

Algorithm

Start with an empty combination and a starting index of 1.
If the combination size equals k, save a copy to the result and return.
Iterate from the start index to n. For each number, add it to the combination.
Recursively call with start = i + 1 to only consider larger numbers.
Remove the last element (backtrack) before trying the next number.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []

        def backtrack(start, comb):
            if len(comb) == k:
                res.append(comb.copy())
                return

            for i in range(start, n + 1):
                comb.append(i)
                backtrack(i + 1, comb)
                comb.pop()

        backtrack(1, [])
        return res

public class Solution {
    private List<List<Integer>> res;

    public List<List<Integer>> combine(int n, int k) {
        res = new ArrayList<>();
        backtrack(1, n, k, new ArrayList<>());
        return res;
    }

    private void backtrack(int start, int n, int k, List<Integer> comb) {
        if (comb.size() == k) {
            res.add(new ArrayList<>(comb));
            return;
        }

        for (int i = start; i <= n; i++) {
            comb.add(i);
            backtrack(i + 1, n, k, comb);
            comb.remove(comb.size() - 1);
        }
    }
}

class Solution {
public:
    vector<vector<int>> res;

    vector<vector<int>> combine(int n, int k) {
        res.clear();
        vector<int> comb;
        backtrack(1, n, k, comb);
        return res;
    }

    void backtrack(int start, int n, int k, vector<int>& comb) {
        if (comb.size() == k) {
            res.push_back(comb);
            return;
        }

        for (int i = start; i <= n; i++) {
            comb.push_back(i);
            backtrack(i + 1, n, k, comb);
            comb.pop_back();
        }
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number[][]}
     */
    combine(n, k) {
        const res = [];

        const backtrack = (start, comb) => {
            if (comb.length === k) {
                res.push([...comb]);
                return;
            }

            for (let i = start; i <= n; i++) {
                comb.push(i);
                backtrack(i + 1, comb);
                comb.pop();
            }
        };

        backtrack(1, []);
        return res;
    }
}

public class Solution {
    public List<List<int>> Combine(int n, int k) {
        List<List<int>> res = new List<List<int>>();

        void Backtrack(int start, List<int> comb) {
            if (comb.Count == k) {
                res.Add(new List<int>(comb));
                return;
            }

            for (int i = start; i <= n; i++) {
                comb.Add(i);
                Backtrack(i + 1, comb);
                comb.RemoveAt(comb.Count - 1);
            }
        }

        Backtrack(1, new List<int>());
        return res;
    }
}

func combine(n int, k int) [][]int {
    res := [][]int{}

    var backtrack func(start int, comb []int)
    backtrack = func(start int, comb []int) {
        if len(comb) == k {
            temp := make([]int, len(comb))
            copy(temp, comb)
            res = append(res, temp)
            return
        }

        for i := start; i <= n; i++ {
            comb = append(comb, i)
            backtrack(i+1, comb)
            comb = comb[:len(comb)-1]
        }
    }

    backtrack(1, []int{})
    return res
}

class Solution {
    fun combine(n: Int, k: Int): List<List<Int>> {
        val res = mutableListOf<List<Int>>()

        fun backtrack(start: Int, comb: MutableList<Int>) {
            if (comb.size == k) {
                res.add(ArrayList(comb))
                return
            }

            for (i in start..n) {
                comb.add(i)
                backtrack(i + 1, comb)
                comb.removeAt(comb.size - 1)
            }
        }

        backtrack(1, mutableListOf())
        return res
    }
}

class Solution {
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        var res = [[Int]]()

        func backtrack(_ start: Int, _ comb: inout [Int]) {
            if comb.count == k {
                res.append(comb)
                return
            }

            for i in start...n {
                comb.append(i)
                backtrack(i + 1, &comb)
                comb.removeLast()
            }
        }

        var comb = [Int]()
        backtrack(1, &comb)
        return res
    }
}

Time & Space Complexity

Time complexity: $O(k * \frac {n!}{(n - k)! * k!})$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

3. Iteration

Intuition

We can simulate backtracking iteratively using an array of size k to track our current combination. An index pointer moves forward when we find valid numbers and backward when we need to backtrack. This eliminates recursion overhead.

Algorithm

Initialize an array of size k with zeros and a pointer i = 0.
Increment comb[i] to try the next value at position i.
If comb[i] exceeds n, move the pointer back (i -= 1) to backtrack.
If i reaches k - 1, we have a complete combination; save it.
Otherwise, move forward (i += 1) and set comb[i] = comb[i - 1] so the next position starts just after the previous value.
Repeat until i becomes negative.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        i = 0
        comb = [0] * k

        while i >= 0:
            comb[i] += 1
            if comb[i] > n:
                i -= 1
                continue

            if i == k - 1:
                res.append(comb.copy())
            else:
                i += 1
                comb[i] = comb[i - 1]

        return res

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        int[] comb = new int[k];
        int i = 0;

        while (i >= 0) {
            comb[i]++;
            if (comb[i] > n) {
                i--;
                continue;
            }

            if (i == k - 1) {
                List<Integer> current = new ArrayList<>();
                for (int num : comb) {
                    current.add(num);
                }
                res.add(current);
            } else {
                i++;
                comb[i] = comb[i - 1];
            }
        }

        return res;
    }
}

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        vector<int> comb(k, 0);
        int i = 0;

        while (i >= 0) {
            comb[i]++;
            if (comb[i] > n) {
                i--;
                continue;
            }

            if (i == k - 1) {
                res.push_back(comb);
            } else {
                i++;
                comb[i] = comb[i - 1];
            }
        }

        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number[][]}
     */
    combine(n, k) {
        const res = [];
        const comb = Array(k).fill(0);
        let i = 0;

        while (i >= 0) {
            comb[i]++;
            if (comb[i] > n) {
                i--;
                continue;
            }

            if (i === k - 1) {
                res.push([...comb]);
            } else {
                i++;
                comb[i] = comb[i - 1];
            }
        }

        return res;
    }
}

public class Solution {
    public List<List<int>> Combine(int n, int k) {
        List<List<int>> res = new List<List<int>>();
        int[] comb = new int[k];
        int i = 0;

        while (i >= 0) {
            comb[i]++;
            if (comb[i] > n) {
                i--;
                continue;
            }

            if (i == k - 1) {
                res.Add(new List<int>(comb));
            } else {
                i++;
                comb[i] = comb[i - 1];
            }
        }

        return res;
    }
}

func combine(n int, k int) [][]int {
    res := [][]int{}
    comb := make([]int, k)
    i := 0

    for i >= 0 {
        comb[i]++
        if comb[i] > n {
            i--
            continue
        }

        if i == k-1 {
            temp := make([]int, k)
            copy(temp, comb)
            res = append(res, temp)
        } else {
            i++
            comb[i] = comb[i-1]
        }
    }

    return res
}

class Solution {
    fun combine(n: Int, k: Int): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        val comb = IntArray(k)
        var i = 0

        while (i >= 0) {
            comb[i]++
            if (comb[i] > n) {
                i--
                continue
            }

            if (i == k - 1) {
                res.add(comb.toList())
            } else {
                i++
                comb[i] = comb[i - 1]
            }
        }

        return res
    }
}

class Solution {
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        var res = [[Int]]()
        var comb = [Int](repeating: 0, count: k)
        var i = 0

        while i >= 0 {
            comb[i] += 1
            if comb[i] > n {
                i -= 1
                continue
            }

            if i == k - 1 {
                res.append(comb)
            } else {
                i += 1
                comb[i] = comb[i - 1]
            }
        }

        return res
    }
}

Time & Space Complexity

Time complexity: $O(k * \frac {n!}{(n - k)! * k!})$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

4. Bit Manipulation

Intuition

Each subset of numbers from 1 to n can be represented as an n-bit binary number, where bit i being set means number (i+1) is included. We iterate through all possible bitmasks and keep only those with exactly k bits set.

Algorithm

Iterate through all integers from 0 to 2^n - 1. Each integer represents a possible subset.
For each mask, extract the numbers corresponding to set bits (if bit j is set, include j + 1).
If the resulting subset has exactly k elements, add it to the result.
Return all valid combinations.

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        res = []
        for mask in range(1 << n):
            comb = []
            for bit in range(n):
                if mask & (1 << bit):
                    comb.append(bit + 1)

            if len(comb) == k:
                res.append(comb)
        return res

public class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> res = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> comb = new ArrayList<>();
            for (int bit = 0; bit < n; bit++) {
                if ((mask & (1 << bit)) != 0) {
                    comb.add(bit + 1);
                }
            }
            if (comb.size() == k) {
                res.add(comb);
            }
        }
        return res;
    }
}

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> res;
        for (int mask = 0; mask < (1 << n); ++mask) {
            vector<int> comb;
            for (int bit = 0; bit < n; ++bit) {
                if (mask & (1 << bit)) {
                    comb.push_back(bit + 1);
                }
            }
            if (comb.size() == k) {
                res.push_back(comb);
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number} n
     * @param {number} k
     * @return {number[][]}
     */
    combine(n, k) {
        const res = [];
        for (let mask = 0; mask < 1 << n; mask++) {
            if (mask.toString(2).split('1').length - 1 !== k) {
                continue;
            }

            const comb = [];
            for (let bit = 0; bit < n; bit++) {
                if (mask & (1 << bit)) {
                    comb.push(bit + 1);
                }
            }
            res.push(comb);
        }
        return res;
    }
}

public class Solution {
    public List<List<int>> Combine(int n, int k) {
        List<List<int>> res = new List<List<int>>();

        for (int mask = 0; mask < (1 << n); mask++) {
            List<int> comb = new List<int>();
            for (int bit = 0; bit < n; bit++) {
                if ((mask & (1 << bit)) != 0) {
                    comb.Add(bit + 1);
                }
            }
            if (comb.Count == k) {
                res.Add(comb);
            }
        }

        return res;
    }
}

class Solution {
    fun combine(n: Int, k: Int): List<List<Int>> {
        val res = mutableListOf<List<Int>>()
        for (mask in 0 until (1 shl n)) {
            val comb = mutableListOf<Int>()
            for (bit in 0 until n) {
                if (mask and (1 shl bit) != 0) {
                    comb.add(bit + 1)
                }
            }
            if (comb.size == k) {
                res.add(comb)
            }
        }
        return res
    }
}

class Solution {
    func combine(_ n: Int, _ k: Int) -> [[Int]] {
        var res = [[Int]]()
        for mask in 0..<(1 << n) {
            var comb = [Int]()
            for bit in 0..<n {
                if mask & (1 << bit) != 0 {
                    comb.append(bit + 1)
                }
            }
            if comb.count == k {
                res.append(comb)
            }
        }
        return res
    }
}

impl Solution {
    pub fn combine(n: i32, k: i32) -> Vec<Vec<i32>> {
        let mut res = Vec::new();
        for mask in 0..(1 << n) {
            let mut comb = Vec::new();
            for bit in 0..n {
                if mask & (1 << bit) != 0 {
                    comb.push(bit + 1);
                }
            }
            if comb.len() == k as usize {
                res.push(comb);
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n * 2 ^ n)$
Space complexity: $O(k * \frac {n!}{(n - k)! * k!})$ for the output array.

Where $n$ is the number of elements and $k$ is the number of elements to be picked.

Common Pitfalls

Forgetting to Copy the Combination Before Adding to Results

When adding the current combination to the result list, you must create a copy. Otherwise, subsequent modifications during backtracking will alter the already-added result.

# Wrong: adds reference that gets modified
res.append(comb)

# Correct: adds a copy
res.append(comb.copy())

Missing the Backtrack Step

After exploring a branch with an element included, you must remove it before exploring the next branch. Forgetting to pop leads to combinations with too many elements.

comb.append(i)
backtrack(i + 1, comb)
# Missing: comb.pop()

Using Wrong Loop Bounds

Starting the loop at 0 instead of start causes duplicate combinations like [1,2] and [2,1]. The loop must start from the current position to ensure each combination is generated only once in sorted order.