1464. The K-th Combination

Code(Language:C++)

class Solution {
public:
    /**
     * @param n: The integer n
     * @param k: The integer k
     * @return: Return the combination
     */
    vector<int> getCombination(int n, int k) {
        // Write your code here
        vector<int> res;
        vector<int> sub; 
        int cnt = 0; 
        dfs(n, k, 1, cnt, res, sub);
        return res; 
    }
    void dfs(int n, int k, int start, int &cnt, vector<int> &res, vector<int> &subset){
        if(cnt > k){
            return; 
        }
        if(subset.size() == n / 2){
            cnt++; 
            if(cnt == k){
                res = subset; 
            }
            return; 
        }
        for(int i = start; i <= n; i++){
            subset.push_back(i); 
            dfs(n, k, i + 1, cnt, res, subset); 
            subset.pop_back(); 
        }
    }
};