Combinations

77.Combinations

Backtracking

Recursion

Math

Problem Statement:

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:

Input:

n = 4, k = 2

→

Output:

[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Algorithm:

1. Use backtracking to build combinations
2. Keep track of current numbers in combination
3. Start from increasing indexes to avoid duplicates
4. Add when size reaches k

Complexity:

Time: O(N choose K) | Space: O(K)

Java Solution:

public ListInteger>> combine(int n, int k) {
    ListInteger>> res = new ArrayList<>();
    // Start backtracking from index 1
    combine(n, k, res, new ArrayList<>(), 1);
    return res;  
}

private void combine(int n, int k, 
        ListInteger>> res, List<Integer> temp, int index) {
    
    // Found a valid combination
    if (temp.size() == k) {
        res.add(new ArrayList<>(temp));
        return;
    }
    
    // Try all possible numbers from current index
    for (int i = index; i <= n; i++) {
        temp.add(i);  // Choose
        combine(n, k, res, temp, i + 1);  // Explore
        temp.remove(temp.size() - 1);  // Unchoose
    }
}

Python Solution:

def combine(self, n: int, k: int) -> List[List[int]]:
    result = []
    
    def backtrack(start: int, curr: List[int]):
        # Found a valid combination
        if len(curr) == k:
            result.append(curr[:])
            return
            
        # Try remaining numbers
        for i in range(start, n + 1):
            curr.append(i)
            backtrack(i + 1, curr)
            curr.pop()
            
    backtrack(1, [])
    return result

C++ Solution:

class Solution {
private:
    void backtrack(vectorint>>& result, 
            vector<int>& curr, int n, int k, int start) {
        if (curr.size() == k) {
            result.push_back(curr);
            return;
        }
        
        for (int i = start; i <= n; i++) {
            curr.push_back(i);
            backtrack(result, curr, n, k, i + 1);
            curr.pop_back();
        }
    }
    
public:
    vectorint>> combine(int n, int k) {
        vectorint>> result;
        vector<int> curr;
        backtrack(result, curr, n, k, 1);
        return result;
    }
};