77. Combinations.md

77. Combinations

• Difficulty: Medium.
• Related Topics: Backtracking.
• Similar Questions: Combination Sum, Permutations.

Problem

Given two integers n and k, return all possible combinations of k numbers out of 1 ... 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 || k < 1) return [];
  
  var res = [];
  
  helper(res, [], 0, n, k);
  
  return res;
};

var helper = function (res, now, start, n, k) {
  if (k === 0) {
    res.push(Array.from(now));
    return;
  }

  for (var i = start; i < n; i++) {
    now.push(i + 1)
    helper(res, now, i + 1, n, k - 1);
    now.pop();
  }
};

Explain:

nope.

Complexity:

• Time complexity :
• Space complexity :