Last updated on March 2nd, 2025 at 05:22 pm

Here, we see a Combinations LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

Backtracking

Level of Question

Medium

Combinations LeetCode Solution

1. Problem Statement

Given two integers n and k, return all possible combinations of k numbers are 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.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Subsets”. This pattern is used to generate all possible combinations (or subsets) of a given size k from a set of numbers ranging from 1 to n. The problem involves recursive backtracking or combinatorial logic to explore all possible subsets.

3. Code Implementation in Different Languages

3.1 Combinations C++

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> temp;
        vector<vector<int>> ans;
        
        help(1, temp, ans, n, k);
        return ans;
    }
    
    void help(int num, vector<int> &temp, vector<vector<int>> &ans, int n, int k){
        if(temp.size() == k){
            ans.push_back(temp);
            return;
        }
        for(int i=num; i<=n; i++){
            temp.push_back(i);
            help(i+1, temp, ans, n, k);
            temp.pop_back();   
        }        
    }
};

3.2 Combinations Java

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (k > n || k < 0) {
            return result;
        }
        if (k == 0) {
            result.add(new ArrayList<Integer>());
            return result;
        }
        result = combine(n - 1, k - 1);
        for (List<Integer> list : result) {
            list.add(n);
        }
        result.addAll(combine(n - 1, k));
        return result;
    }
}

3.3 Combinations JavaScript

var combine = function(n, k) {
    if (n == 1 && k == 1) return [[1]];
    let out = [];
    const dfs = (currentSolution, startNumber, out) => {
        if (currentSolution.length == k) out.push(Array.from(currentSolution));
        for (let i = startNumber; i <= n; i++) {
            currentSolution.push(i);
            dfs(currentSolution, i + 1, out);
            currentSolution.pop();
        }
    }
    dfs([], 1, out);
    return out;
};

3.4 Combinations Python

class Solution(object):
    def combine(self, n, k):
        if k == 0:
            return [[]]
        return [pre + [i] for i in range(k, n+1) for pre in self.combine(i-1, k-1)]

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(C(n, k) * k)	O(k)
Java	O(C(n, k) * k)	O(k)
JavaScript	O(C(n, k) * k)	O(k)
Python	O(C(n, k) * k)	O(k)

• C(n, k) is the binomial coefficient, which is equal to n! / (k! * (n-k)!). It represents the number of ways to choose k elements from a set of n elements.
• C(n, k) grows exponentially with n and k, so the algorithm is computationally expensive for large inputs.
• The recursive backtracking approach is efficient for generating combinations but can be memory-intensive if the result list is large.
• The recursive nature of the code ensures that all combinations are explored systematically, and backtracking ensures no duplicate combinations are generated.
• The Python implementation is concise but may be less intuitive for beginners due to its use of list comprehensions with recursion.
• The space complexity does not include the result list because it is part of the output and not auxiliary space.