Combinations Problem Solution [Leetcode]

Combinations Problem Solution: Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

You may return the answer in any order.

Example :

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

Combinations Problem Solution

Problem Solution In Python

def combine(self, n: int, k: int) -> List[List[int]]:
        nums=[]
        for i in range(1,n+1,1):
            nums.append(i)
        temp=[]
        result=[]
        def dfs(m,num):
            if m==k:
                result.append(temp[:])
                return
            else:
                if len(num)<k-m:
                    return
                for i in range(len(num)):
                    temp.append(num[i])
                    dfs(m+1,num[i+1:])
                    temp.pop()
        dfs(0,nums)
        return result

Problem Solution In Java

class Solution {
    public List<List<Integer>> combine(int n, int k) {
        int[] nums=new int[n];
        for(int i=1;i<=n;i++)
        {
            nums[i-1]=i;
        }
        List<List<Integer>> ans=new ArrayList<>();
        List<Integer> ls=new ArrayList<>();
        helper(nums,k,ls,ans,0);
        return ans;
    }
    private void helper(int[] nums,int k,List<Integer> ls,List<List<Integer>> ans,int start)
    {
        if(ls.size()==k)
        {
            ans.add(new ArrayList<>(ls));
        }
        else
        {
            for(int i=start;i<nums.length;i++)
            {
                ls.add(nums[i]);
                helper(nums,k,ls,ans,i+1);
                ls.remove(ls.size()-1);
            }
        }
    }

}

Problem Solution In C++

class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> output;
        vector<int> combination;
        combine(output, combination, n, k, 1);
        return output;
    }

private:
    void combine(vector<vector<int>>& output, vector<int> combination, int n, int k, int i) {
        if (combination.size() == k) {
            output.push_back(combination);
            return;
        }
        for (int j = i; j <= n; j++) {
            combination.push_back(j);
            combine(output, combination, n, k, j + 1);
            combination.pop_back();
        }
    }
};

Problem Solution In C

int Com(int n, int k) {
    long int no = 1;
    long int de = 1;
    for (int i = 1; i < k+1; i++) {
        de *= i;
    }
    for (int i = 0; i < k; i++) {
        no *= (n-i);
    }
    return no / de;
}

int** combine(int n, int k, int* returnSize, int** returnColumnSizes){
    int total = Com(n,k);
    *returnSize = total;
    int cnt = 0, j = 0;
    int *K = malloc(sizeof(int) * k);
    K[0] = 0;
    for (int i = 1; i < k; i++) {
        K[i] = K[i-1] + 1;
    }
    int ** res = malloc(sizeof(int *) * total);
    (*returnColumnSizes) = malloc(sizeof(int) * total);
    for (int i = 0; i < total; i++) {
        (*returnColumnSizes)[i] = k;
        res[i] = malloc(sizeof(int) * k);
        for (j = 0; j < k; j++) {
            res[i][j] = 1 + K[j];
        }
        if (i == total-1) {
            break;
        }
        K[k-1]++;
        cnt = 0;
        while ((K[k-1-cnt] > n - cnt - 1) && (k - cnt != 1)) {
            cnt++;
            K[k-1-cnt]++;
        }
        for (j = cnt; j > 0; j--) {
            K[k-j] = K[k-1-j] + 1;
        }
    }
    return res;
}