77. Combinations

Medium

Problem Description

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.

Examples

Example 1:
Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 6 possible combinations.

Example 2:
Input: n = 1, k = 1
Output: [[1]]
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


def combine(n: int, k: int) -> List[List[int]]:
    def backtrack(start: int, curr: List[int]):
        if len(curr) == k:
            result.append(curr[:])
            return
        
        for i in range(start, n + 1):
            curr.append(i)
            backtrack(i + 1, curr)
            curr.pop()
    
    result = []
    backtrack(1, [])
    return result

Java Solution


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

C++ Solution


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

JavaScript Solution


/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    const result = [];
    
    function backtrack(start, curr) {
        if (curr.length === k) {
            result.push([...curr]);
            return;
        }
        
        for (let i = start; i <= n; i++) {
            curr.push(i);
            backtrack(i + 1, curr);
            curr.pop();
        }
    }
    
    backtrack(1, []);
    return result;
};

C# Solution


public class Solution {
    private IList> result;
    
    public IList> Combine(int n, int k) {
        result = new List>();
        Backtrack(n, k, 1, new List());
        return result;
    }
    
    private void Backtrack(int n, int k, int start, List curr) {
        if (curr.Count == k) {
            result.Add(new List(curr));
            return;
        }
        
        for (int i = start; i <= n; i++) {
            curr.Add(i);
            Backtrack(n, k, i + 1, curr);
            curr.RemoveAt(curr.Count - 1);
        }
    }
}

Complexity Analysis

Solution Explanation

This solution uses backtracking to generate all possible combinations:

Key points: