LeetCode: Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

---

We can use the same idea as generating permutation here.

C++ Code:

/*
 * func: combination_helper
 * goal: helper function for combination
 * @param start: number start to find
 * @param n: total number
 * @param k: total selected number
 * @param comb: current combination
 * @param result: final result set
 * return:
 */
void combination_helper(int start, int n, int k, vector<int> &comb, vector<vector<int> > &result){
    if(comb.size() == k){
        result.emplace_back(comb);
        return;
    }
    for(int i = start; i <= n; ++i){
        comb.emplace_back(i);
        combination_helper(start+1, n, k, comb, result);
        comb.pop_back();
    }
}

/*
 * func: combination
 * goal: find all combinations of k numbers in n
 * @param n:
 * @param k:
 * return: all possible combinations
 */
vector<vector<int> > combination(int n, int k){
    vector<vector<int> > result;
    if(!(n > 0 && k > 0 && n >=k)){
        return result;
    }
    vector<int> comb;
    combination_helper(1, n, k, comb, result);
    return result;
}

Python Code:

# func: compute combinations
# @param n:
# @param k:
# @return: all combinations
def combinations(n, k):
    if not n >= k > 0:
        return []

    result = []
    comb = []

    def combination_helper(curr):
        if len(comb) == k:
            result.append(comb[:])
            return

        for i in xrange(curr, n+1):
            comb.append(i)
            combination_helper(i+1)
            comb.pop(-1)

    combination_helper(1)
    return result