This is my working solution for the following problem: given an array of integers of size n, print all possible combinations of size r.
Before I proceed to the solution, I have the following question: combination means that the order does not matter, right? I.e. printing {1, 2}
is the same as {2, 1}
, so I want to avoid repetitions?
If yes, here is what I do to avoid printing duplicate combinations: presort the given array arr
, and if for some i
I have that arr[i] == arr[i+1]
I just skip this iteration.
Is my approach correct? Is there better solution?
package recursion;
import java.util.Arrays;
public class Combinations {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 4, 5};
int r = 3;
Arrays.sort(arr);
combine(arr, r);
}
private static void combine(int[] arr, int r) {
int[] res = new int[r];
doCombine(arr, res, 0, 0, r);
}
private static void doCombine(int[] arr, int[] res, int currIndex, int level, int r) {
if(level == r){
printArray(res);
return;
}
for (int i = currIndex; i < arr.length; i++) {
res[level] = arr[i];
doCombine(arr, res, i+1, level+1, r);
//way to avoid printing duplicates
if(i < arr.length-1 && arr[i] == arr[i+1]){
i++;
}
}
}
private static void printArray(int[] res) {
for (int i = 0; i < res.length; i++) {
System.out.print(res[i] + " ");
}
System.out.println();
}
}