Combinations

MEDIUM

Description

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 = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Example 2:

Input: n = 1, k = 1
Output: [[1]]
Explanation: There is 1 choose 1 = 1 total combination.

Constraints:

1 <= n <= 20
1 <= k <= n

Approaches

Checkout 2 different approaches to solve Combinations. Click on different approaches to view the approach and algorithm in detail.

Brute Force: Generate All Subsets and Filter

A straightforward but inefficient method is to generate all possible subsets of numbers from the range [1, n] and then select only those subsets that have a size of k. The total number of subsets for a set of n elements is 2^n. We can represent each subset using a bitmask of length n, where the i-th bit being set indicates the presence of the number i+1 in the subset.

Algorithm

Initialize an empty list result to store the final combinations.
The total number of subsets of n elements is 2^n. We can iterate through all numbers from 0 to 2^n - 1.
Each number i in this range can be treated as a bitmask of length n.
For each bitmask i:
- Create a new empty list currentCombination.
- Iterate from j = 0 to n-1.
- If the j-th bit of i is 1 (checked using (i >> j) & 1), it signifies that the number j+1 is part of the subset. Add j+1 to currentCombination.
After constructing the subset, check if currentCombination.size() is equal to k.
If it is, add currentCombination to the result list.
After checking all 2^n bitmasks, return the result list.

The algorithm iterates through all numbers from 0 to 2^n - 1. Each number i serves as a bitmask. For each bitmask i, we construct a corresponding subset. We iterate from j = 0 to n-1. If the j-th bit of i is set, it means the number j+1 is included in the current subset. After constructing a subset, we check if its size is equal to k. If the size is k, we add this subset to our final list of results. This process continues until all 2^n possible subsets have been checked.

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        // Iterate through all possible subsets represented by bitmasks
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> currentCombination = new ArrayList<>();
            // Check which numbers are in the current subset
            for (int j = 0; j < n; j++) {
                if (((i >> j) & 1) == 1) {
                    currentCombination.add(j + 1);
                }
            }
            // If the subset has size k, add it to the result
            if (currentCombination.size() == k) {
                result.add(currentCombination);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n * 2^n)Space Complexity: O(k)

Pros and Cons

Pros:

Conceptually simple if you are familiar with bit manipulation for generating subsets.
It's an iterative approach that avoids recursion.

Cons:

Highly inefficient due to its exponential time complexity O(n * 2^n).
Generates a large number of unnecessary subsets of sizes other than k, leading to wasted computation.

Code Solutions

Checking out 4 solutions in different languages for Combinations. Click on different languages to view the code.

Video Solution

Watch the video walkthrough for Combinations

Patterns:

Backtracking

Companies:

Adobe |Amazon |Apple |Bloomberg |