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;
}


If You Like This Page Then Make Sure To Follow Us on Facebook, G News and Subscribe Our YouTube Channel. We will provide you updates daily.
Shares
facebook sharing button Share
twitter sharing button Tweet
whatsapp sharing button Share
telegram sharing button Share
pinterest sharing button Pin

Leave a Comment