Find all distinct combinations of a given length

Posted in

Find all distinct combinations of a given length
vinaykhatri

Vinay Khatri
Last updated on April 14, 2024

    Problem

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

    Sample Input

    N = 4, K = 2

    Sample Output

    1 2 
    1 3 
    1 4 
    2 3 
    2 4 
    3 4

    Explanation

    All the combinations have size 2 and lie in the range 1-4

    Approach

    This question is designed to test our knowledge of recursion and backtracking. We can just brute force for all possible combinations in order to accomplish our task. Each element can either be a part of a combination or cannot be. We recursively apply these two conditions and find all possible results.

    Complexity Analysis

    The time complexity of this approach would go exponential as we are finding all possible combinations.

    C++ Programming

    #include<bits/stdc++.h>
    using namespace std;
     vector<vector<int>>res;
        vector<int>v;
        void find(int i, int n, int k,vector<int> &p)
    {
        if(k == 0)
        {
            res.push_back(p);
            return;
        }
        
        if(i >= n)
            return ;
        
        p.push_back(v[i]);
        find(i+1,n,k-1,p);
        p.pop_back();
        find(i+1,n,k,p);
    }
    
    vector<vector<int>> combine(int n, int k)
    {
        for(int i = 1; i <= n; i++)
        v.push_back(i);
        
        vector<int> p;
        find(0,n,k,p);
        
        return res;
    }
    int main(){
        int n = 4, k=2;
        vector<vector<int>>res=combine(n,k);
        for(auto itr:res){
            for(auto e: itr) cout<<e<<" ";
            cout<<"\n";
        }
        
    }

    Output

    1 2
    1 3 
    1 4 
    2 3 
    2 4 
    3 4

    Python Programming

    def combine(n, k):
            res = []
            nums = [i+1 for i in range(n)]
            def getCombination(candidate, next_nums, k):
                if k == 0:
                    res.append(candidate)
                    return
                for i in range(0, len(next_nums)):
                    if len(next_nums) >= k:
                        getCombination(candidate+[next_nums[i]], next_nums[i+1:], k-1)
            
            getCombination([], nums, k)
            return res
    
    n = 4
    k = 2
    print(combine(n,k))
    

    Output

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

    Java Programming

    import java.util.*;  
    class Solution {
        public static List<List<Integer>> combine(int n, int k) {
            return (solve(1,k,n));
        }
        
        public static List<List<Integer>> solve(int l,int k,int n)     //l is the starting index
        {
            int limit=n-k+1;        /*this gives us a limit uptil which we can make
                                    possible sets of size k*/
            List<List<Integer>> ans=new ArrayList<>();
            if(k==1)                        //if k==1 then add all the possible numbers
            {                               //starting from l
                for(int i=l;i<=n;i++)
                {
                    List<Integer> li=new ArrayList<>();
                    li.add(i);
                    ans.add(li);
                }
                return ans;
            }
            for(int i=l;i<=limit;i++)
            {
                List<List<Integer>> li=solve(i+1,k-1,n);    /*We get the list and add i to the current list and add it as a resultant to the ans list*/
                add(i,li,ans);
            }
            return ans;
        }
    
        public static void add(int i,List<List<Integer>> li, List<List<Integer>> ans)
        {
            for(List<Integer> l:li)
            {
                l.add(0,i);
                ans.add(l);
            }
        }
    
        public static void main(String args[])
        {
            int n = 4, k = 2;
            System.out.println(combine(n, k));
        }
    
        
    }

    Output

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

    People are also reading:

    Leave a Comment on this Post

    0 Comments