77. Combinations

• Difficulty: Medium

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

Solutions:

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<int> path;
        vector<vector<int>> ret;
        helper(n, k, 1, path, ret);
        return ret;
    }

    void helper(int n, int k, int pos, vector<int>& path, vector<vector<int>>& ret) {
        if (path.size() == k) {
            ret.push_back(path);
            return;
        }

        if (pos > n || n - pos + 1 + path.size() < k) {
            return;
        }

        path.push_back(pos);
        helper(n, k, pos + 1, path, ret);      
        path.pop_back();
        helper(n, k, pos + 1, path, ret);
    }
};