Combinations

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

If n = 4 and k = 2, a solution is: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

http://www.lintcode.com/en/problem/combinations/

Discussion

These combinations of k numbers are from one category, i.e., with the dimension K, of the subsets of n numbers. So it is the same as the Subsets question, except the output condition is dim==k.

Solution

class Solution {
public:
    /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    vector<vector<int> > combine(int n, int k) {
        // write your code here
        vector<vector<int> > result;
        if(n==0 || k>n) return result;
        vector<int> resolution (k, 0);//solution只用k维就可以了，因为就是输出k维
        backtracing(n, k, 0, 1, resolution, result);
        return result;
    }
private: 

    void backtracing(int n, int k, int dim, int start, 
            vector<int> &solution, vector<vector<int> > &rec) {
        if(dim == k) {//只输出长度为k的子集
            vector<int> subset;
            for(int i=0; i<dim; i++) {
                subset.push_back(solution[i]);
            }
            rec.push_back(subset);
            return;//不用再tracing下一维了，所以return，不然n大的时候会超时。
        }
        for(int i=start; i<=n; i++) {//跟subsets问题一样的
            solution[dim] = i;
            backtracing(n, k, dim+1, i+1, solution, rec);
        }
    }
};

DFS solution. 用的还是Subsets的模板。

class Solution {
public:
    /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    vector<vector<int> > combine(int n, int k) {
        // write your code here
        vector<vector<int> > result;
        vector<int> path;
        dfs(n, k, result, path, 1);
        return result;
    }
    void dfs(int n, int k, vector<vector<int> > &records, vector<int> &path, int pos) {
        if(path.size() == k) {
            records.push_back(path);
            return;
        }
        for(int i=pos; i<=n; i++) {
            path.push_back(i);
            dfs(n, k, records, path, i+1);
            path.pop_back();
        }
    }
};

Itereation solution. 在Subsets的迭代版上修改。

class Solution {
public:
    /**
     * @param n: Given the range of numbers
     * @param k: Given the numbers of combinations
     * @return: All the combinations of k numbers out of 1..n
     */
    vector<vector<int> > combine(int n, int k) {
        // write your code here
        vector<vector<int> > result;//subsets的result，但是只保存size小于k的subset
        vector<vector<int> > resultFinal;
        if(n==0) return result;
        vector<int> none;
        if(k==0) {
            resultFinal.push_back(none);
            return resultFinal;
        }
        result.push_back(none);
        for(int i=1; i<=n; i++) {
            vector<vector<int> > tmp = result;
            for(int j=0; j<tmp.size(); j++) {//当前结果里面每个子集都添加当前新元素nums[i]
                tmp[j].push_back(i);
                if(tmp[j].size() == k) {//等于k的时候输出
                    resultFinal.push_back(tmp[j]);
                } else {
                    result.push_back(tmp[j]);//小于k
                }
            }
        }
        return resultFinal;
    }
};