组合.md

Combinations

Given two integers n and k, return all possible combinations of k numbers from 1 to n.

Example

Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    if(n <= k) return [[...new Array(n).keys()].map(v => v+1)];
    var target = [];
    var dfs = function(cur, deep, tmp){
        if (tmp.length + (n - cur + 1) < k) return void 0;
        if(deep === k){
            target.push(tmp);
            return void 0;
        }
        for(;cur<=n;++cur) dfs(cur+1, deep+1, [...tmp, cur]);
    }
    dfs(1, 0, []);
    return target;
};

Idea

Taking the values in the example as an example, it can be considered as an array of length 4 [1, 2, 3, 4]. Each pair of two forms an array. We can take 1 along with the remaining values in its array, 2 along with the remaining values in its array, 3 along with the remaining values in its array, 4 along with the remaining values in its array, which are [1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]. First, the initial condition is judged. If n <= k, only an array of length n can be formed, which can be placed in a two-dimensional array and returned. Later, the expression uses new Array(n) to generate an empty array of length n, gets its keys iterator, and uses ... or Spread operator to expand it. Then it uses map to process it as key value +1. After that, the target array is defined. Then the dfs recursion function is defined. First, pruning is performed. If the size of the current tmp array is s and the length of the undetermined interval [cur,n] is t, if s + t < k, even if t is all selected, it is not possible to construct a sequence of length k, so it is not necessary to continue to recurse downward in this case. Then, if the recursive depth is equal to k, the tmp array is directly placed into the target array and returned. After that, a loop is defined, and recursion is performed from cur to n. The tmp array and cur are used to form a new array to be passed to the next recursion. Then the recursion is started with cur initialized to 1, deep to 0, and tmp as an empty array. After the recursion is completed, the target array is returned.

Daily Question

https://github.com/WindrunnerMax/EveryDay

Reference

https://leetcode-cn.com/problems/combinations/