Find all distinct combinations of given length – Part 1

Given an array of integers, find all distinct combinations of given length.


 

For example,


Input:  {1, 2, 3}, k = 2
Output: {1, 2}, {1, 3}, {2, 3}
 

Input:  {1, 2, 1}, k = 2
Output: {1, 1}, {1, 2}

 
The program should print only distinct combinations. For example, for above input, either {1, 2} or {2, 1} should be considered.
 

 

We can use recursion to solve this problem. The idea is to add each element in the output and recurse for remaining elements with one less element. To avoid printing permutations, each combination will be constructed in same order as array elements. If combination of given size is found, we print it. Below solution generates all combinations by using above logic by traversing the array from left to right. To print only distinct combinations in case input contains repeated elements, we can sort the array and exclude all adjacent duplicate elements from the array.

C++

Download   Run Code

Output:

1 2
1 3
2 3

Java

Download   Run Code

Output:

1 2
1 3
2 3

 
We can also process the elements of the array from right to left. The idea is illustrated below –

C++

Download   Run Code

Output:

2 3
1 3
1 2

Java

Download   Run Code

Output:

2 3
1 3
1 2

 
Another Approach: Find all distinct combinations of given length – Part 2

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 



Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Rishabh Jain
Guest

To avoid duplicates, the while loop should come before recursion call

dragonite
Guest

It won’t work for all cases.
Eg: {10, 9, 10, 9, 10 }, k=5.

Aditya
Guest

Seems to work – https://ideone.com/9jk1Rk
What other output were you expecting?

Bhoomit
Guest

How is one loop inside another different from this? This is also n^2 if I’m not wrong.