1. Leetcode 77. Combinations

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], ]

2. Solution

2.1. Solution 1: DFS

// Runtime: 104 ms, faster than 71.52% of C++ online submissions for Combinations.
// Memory Usage: 11.7 MB, less than 100.00% of C++ online submissions for Combinations.
class Solution {
 public:
  vector<vector<int>> combine(int n, int k) {
    vector<vector<int>> ans;
    vector<int> out;
    ans.reserve(k);
    combineDFS(n, k, 1, out, ans);
    return ans;
  }

 private:
  void combineDFS(int n, int k, int index, vector<int>& out, vector<vector<int>>& ans) {
    if (k == 0) {
      ans.emplace_back(out);
      return;
    }
    for (int i = index; i <= n; ++i) {
      out.emplace_back(i);
      combineDFS(n, k - 1, i + 1, out, ans);
      out.pop_back();
    }
  }
};

3. Updated

• 03/01/2019 Review(BFS: 5 mins)