Combinations Editorial

Practice Problem Link: Combinations

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given two integers n and k, return all possible combinations of size k containing distinct numbers between 1 and n. Note: The list should not contain any duplicate combinations.

Naive Approach

We can generate and store all the unique subsets of size k by using Bitmasking and then return the calculated list.

Analysis

• Time Complexity: O(n * 2ⁿ)
• Space Complexity: O(k * nCk)

Optimal Approach

We can solve this problem by brute force recursion with backtracking. At each point, we have two choices, take the current element in the set, or don't take this element. We keep storing the current list of the size k, based on this rule of considering or not considering the current element till k equals 0, which means that we have exhausted the size of our list.

Analysis

• Time Complexity: O(k * nCk)
• Space Complexity: O(k * nCk)

Implementation

C++

void combinationsUtil(int curr, int n, int k, vector<vector<int> > &result, vector<int> &current) {
	if (k == 0) {
		result.push_back(current);
	}
	
	for (int i = curr; i <= n; i++) {
		current.push_back(i);
		combinationsUtil(i + 1, n, k - 1, result, current);
		current.pop_back();
	}
}

vector<vector<int> > combinations(int n, int k) {
    // add your logic here
	vector<vector<int> > result = vector<vector<int> >();
	vector<int> current = vector<int>();
	combinationsUtil(1, n, k, result, current);
	return result;
}

Java

class Solution {
	public void combinationsUtil(int curr, int n, int k, List<List<Integer>> result, List<Integer> current) {
		if (k == 0) {
			result.add(new ArrayList<>(current));
		}

		for (int i = curr; i <= n; i++) {
			current.add(i);
			combinationsUtil(i + 1, n, k - 1, result, current);
			current.remove(current.size() - 1);
		}
	}

	List<List<Integer>> combinations(int n, int k) {
	    // add your logic here
		List<List<Integer>> result = new ArrayList<List<Integer>>();
		List<Integer> current = new ArrayList<Integer>();
		combinationsUtil(1, n, k, result, current);
		return result;
	}
}