77. Combinations Medium

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 1:
Input: n = 4, k = 2
Output:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ]

Example 2:
Input: n = 1, k = 1
Output: [[1]]

Approach

Input: Two integers n and k

Output: Return all possible combinations of k numbers chosen from the range [1, n]

This problem belongs to Combination Backtracking problems.

Three Questions of Backtracking

1. Current Operation?
   • At the current position i, try to choose a number j and place it into path.
   • That is: place the number j (j ∈ [i, 1]) into the path path, indicating "I have selected it".
2. Sub-problem?
   • After choosing the number j, we need to continue selecting the remaining numbers, and the maximum value of the remaining numbers cannot exceed j-1 (because we cannot select repeatedly).
   • That is: recursively call dfs(j-1) to continue constructing the remaining combination.
3. Next Sub-problem?
   • The next recursive step starts from dfs(j-1), continuing to pick numbers.
   • This is the "branching down", meaning continuing to choose from the remaining numbers.

Pruning Conditions

• When the number of remaining available digits is smaller than k - len(path), there is no need to try anymore, because it is impossible to gather k numbers.

Implementation

python

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []     # Final result, stores all combinations
        path = []    # Current combination path

        def dfs(i):
            # The number of available digits remaining must be ≥ the number of digits still needed
            # Pruning: if the remaining digits are not enough to fill the path, return directly
            if i < k - len(path):
                return

            # If k numbers have been selected, add the current scheme to the result
            if len(path) == k:
                ans.append(path.copy())
                return

            # Pick numbers from largest to smallest to avoid duplicate combinations (each number is picked once)
            for j in range(i, 0, -1):
                path.append(j)      # Select current number
                dfs(j - 1)          # Continue selecting the rest of the numbers
                path.pop()          # Backtrack, undo the choice

        dfs(n)  # Start recursion from n
        return ans

javascript

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
const combine = function(n, k) {
    ans = []
    path = []

    function dfs(i) {
        const d = k - path.length;
        if (i < d) return;

        if (path.length == k) {
            ans.push([...path]);
            return;
        }

        for (let j = i; j > 0; j--) {
            path.push(j);
            dfs(j - 1);
            path.pop();
        }
    }  
    dfs(n);
    return ans;
};

Complexity Analysis

• Time Complexity: O(n * 2^n)
• Space Complexity: O(n * 2^n)

Links

77. Combinations (English)

77. 组合 (Chinese)