77. Combinations

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 (Java)

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        // Boundary case
        if (n > 20 || k < 1 || k > n) {
            return ans;
        }
        backtrack(ans, n, k, 1, new Stack<>());
        return ans;
    }

    private void backtrack(List<List<Integer>> ans, int n, int k, int s, Stack<Integer> stack) {
        // Base case
        // If k becomes 0
        if (k == 0) {
            ans.add(new ArrayList<>(stack));
            return;
        }
        // Start with s till n-k+1
        for (int i = s; i <= (n - k) + 1; i++) {
            stack.push(i);
            // Update start for recursion and decrease k by 1
            backtrack(ans, n, k - 1, i + 1, stack);
            stack.pop();
        }
    }
}

Solution (Javascript)

/**
 * @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 :