# Find all distinct combinations of a given length

Posted in

Vinay Khatri
Last updated on August 11, 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<>();
}
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*/
}
return ans;
}

public static void add(int i,List<List<Integer>> li, List<List<Integer>> ans)
{
for(List<Integer> l:li)
{
}
}

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