Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

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();
    }
}
share|improve this question
    
Combinations = Order does not matter. Permutations = Order does matter. –  Simon André Forsberg Aug 18 at 15:59

1 Answer 1

I think that by avoiding duplicates, you are essentially changing the definition of the question at hand.

If that is indeed the definition of question, then instead of sorting the array and avoiding duplicates, you can simply get rid of the duplicates to begin with by using a set instead of an array:

Set<Integer> set = new HashSet<Integer>();
for (int i : arr)
    set.add(i);

In addition, for better modularity, I think that you should separate the algorithm itself from the printing:

  • Create an empty List<List<Integer>> instance
  • Pass it to the doCombine method, to fill it in with all combinations
  • Print it in the main method (the combine method looks kind of redundant)
share|improve this answer
    
Thanks for the feedback! The definition wasn't clear for me also. I took the question from here: geeksforgeeks.org/… and here they do the same - avoid duplicates, although I'm not sure if we have to do this. I tried to find more formal definition of the question, but I couldn't. –  user3371223 Aug 18 at 15:49
    
You're welcome. The solution I gave above should help you get rid of the duplicate input values "more nicely" than the way that you are doing it now. If the duplicate input values should not be removed (and a combination like 3,4,4 for example is allowed), then you will have the problem of duplicate output values. In order to solve that problem, you can use the second suggestion that I made above, but use HashMap<String,List<Integer>> instead of List<List<Integer>>. You will also have to keep the Arrays.sort(arr) in this case. –  barak manos Aug 18 at 15:56
    
Combinations = Order does not matter. Permutations = Order does matter. So avoiding duplicates should be done. –  Simon André Forsberg Aug 18 at 16:00
    
@SimonAndréForsberg Yes, duplicate results should be avoided ((1,2) shouldn't be in the result if (2,1) already is). But duplicate elements are (generally) allowed (depending on the question). So (2,3,3) should be in the result if the input is [2,3,3]. And that is exactly what the code of OP does. –  tim Aug 18 at 17:10
    
@SimonAndréForsberg: Well then, as I mentioned in the answer, I think that it is "more appropriate" to use a Set, thus remove duplicate values. –  barak manos Aug 18 at 17:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.