Find all distinct combinations of a given length

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:

• Find K-th Smallest Element in BST
• Nth root of M
• Check if directed graph is connected
• Find MSB in O(1)
• Python Take list as an input from a user
• Longest Substring without repeating characters
• Count subarrays with given XOR
• Delete Nodes And Return Forest
• Rearrange an array such that arr[i] = i
• Circular Doubly Linked List