LeetCode 77: Combinations Solution

Master LeetCode problem 77 (Combinations), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

77. Combinations

Medium

Backtracking

Problem Explanation

Explanation

To solve this problem, we can use backtracking to generate all combinations of k numbers chosen from the range [1, n]. The idea is to start from the first number and recursively build the combination list by including or excluding each number. We will keep track of the current combination and the current index being considered. Once the combination reaches the required size (k), we add it to the result list.

Algorithm:

Define a helper function that takes parameters for the current combination list, current index, needed size k, total numbers n, and the result list.
If the current combination size equals k, add it to the result list.
Iterate from the current index up to n:
- Include the current number in the combination list.
- Recur with the next index and updated combination list.
- Exclude the current number from the combination list and move to the next index.

Time Complexity:

The time complexity of this algorithm is O(C(n, k) * k), where C(n, k) is the number of combinations of choosing k elements from n elements.

Space Complexity:

The space complexity is O(k) for the recursion stack and the temporary combination list.

Solution Code

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(result, new ArrayList<>(), 1, n, k);
        return result;
    }
    
    private void backtrack(List<List<Integer>> result, List<Integer> tempList, int start, int n, int k) {
        if(tempList.size() == k) {
            result.add(new ArrayList<>(tempList));
            return;
        }
        
        for(int i = start; i <= n; i++) {
            tempList.add(i);
            backtrack(result, tempList, i + 1, n, k);
            tempList.remove(tempList.size() - 1);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 77 (Combinations)?

This page provides optimized solutions for LeetCode problem 77 (Combinations) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 77 (Combinations)?

The time complexity for LeetCode 77 (Combinations) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 77 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 77 in Java, C++, or Python.

Back to LeetCode Solutions