Scale Engineer

Combinations

Med
#0077Time: O(n * 2^n)Space: O(k)7 companies
Patterns
Backtracking
Companies
AdobeAmazonAppleBloomberg

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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

Time

O(n * 2^n)

Space

O(k)

Trade-offs

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.

Solutions

public class Solution {    private List < IList < int >> ans = new List < IList < int >> ();    private List < int > t = new List < int > ();    private int n;    private int k;    public IList < IList < int >> Combine(int n, int k) {        this.n = n;        this.k = k;        dfs(1);        return ans;    }    private void dfs(int i) {        if (t.Count == k) {            ans.Add(new List < int > (t));            return;        }        if (i > n) {            return;        }        for (int j = i; j <= n; ++j) {            t.Add(j);            dfs(j + 1);            t.RemoveAt(t.Count - 1);        }    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem