5
\$\begingroup\$

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();
    }
}
\$\endgroup\$
4
  • \$\begingroup\$ Combinations = Order does not matter. Permutations = Order does matter. \$\endgroup\$ Aug 18, 2014 at 15:59
  • \$\begingroup\$ this approach is correct. however i wonder if there is a more efficient method to do this. \$\endgroup\$
    – LZH
    Oct 29, 2014 at 0:26
  • \$\begingroup\$ @LZH I solved many such problems after this post, and all af them have the same framework, i.e. for loop and in the for loop is the recursive statement. If you find something better, please tell me. \$\endgroup\$ Oct 31, 2014 at 14:30
  • \$\begingroup\$ i was solving a problem with a slight variation, but this frameworks works for all cases. \$\endgroup\$
    – LZH
    Nov 1, 2014 at 0:24

1 Answer 1

1
\$\begingroup\$

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)
\$\endgroup\$
5
  • \$\begingroup\$ 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. \$\endgroup\$ Aug 18, 2014 at 15:49
  • \$\begingroup\$ 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. \$\endgroup\$ Aug 18, 2014 at 15:56
  • \$\begingroup\$ Combinations = Order does not matter. Permutations = Order does matter. So avoiding duplicates should be done. \$\endgroup\$ Aug 18, 2014 at 16:00
  • \$\begingroup\$ @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. \$\endgroup\$
    – tim
    Aug 18, 2014 at 17:10
  • \$\begingroup\$ @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. \$\endgroup\$ Aug 18, 2014 at 17:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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