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

LeetCode-Combinations

C++:
class Solution {
public:
    vector<vector<int> > combine(int n, int k) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> results;
        vector<int> result;
        if(n<=0||k<=0||n<k) return results;
        comb(n,k,results,result,1,0);
        return results; 
    }
    void comb(int n,int k,vector<vector<int>> &results,vector<int> &result,int start,int num){
        if(num==k){
            results.push_back(result);
            return;
        }
        for(int i=start;i<=n;i++){
            result.push_back(i);
            comb(n,k,results,result,i+1,num+1);
            result.pop_back();
        }
    }
};
Java:
public class Solution {
    public ArrayList<ArrayList<Integer>> combine(int n, int k) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<ArrayList<Integer>> results=new ArrayList<ArrayList<Integer>>();
        if(n<=0||k<=0||n<k) return results;
        ArrayList<Integer> result=new ArrayList<Integer>();
        comb(n,k,results,result,1,0);
        return results;
    }
    public void comb(int n,int k,ArrayList<ArrayList<Integer>>results,ArrayList<Integer> result,int start,int num){
        if(num==k){
            ArrayList<Integer> cur=new ArrayList<Integer>();
            for(Integer i:result) cur.add(i);
            results.add(cur);
            return;
        }
        for(int i=start;i<=n;i++){
            result.add(i);
            comb(n,k,results,result,i+1,num+1);
            result.remove(result.size()-1);
        }
    }
}