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

# Solution

Approach 1: DFS.

# Code (Python)

Approach 1:

# Code (C++)

Approach 1:

class Solution {
private:
    void combine(vector<int>& oneCom, vector<vector<int>>& comSet, int head, int tail, int k) {
        if (k == 0)
        {
            comSet.push_back(oneCom);
            return;
        }
        for (int i = head; i <= tail; ++i)
        {
            oneCom.push_back(i);
            combine(oneCom, comSet, i + 1, tail, k - 1);
            oneCom.pop_back();
        }
    }
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> comSet;
        vector<int> oneCom;
        combine(oneCom, comSet, 1, n, k);
        return comSet;
    }
};