Back

Explore Courses Blog Tutorials Interview Questions
0 votes
1 view
in Java by (7k points)

I have a list of items {a,b,c,d} and I need to generate all the combinations when,

  • You can select any number of items

  • The order is not important (ab=ba)

  • Empty set is not considered

If we take the possibilities, it should be,

n=4, number of items

total #of combinations = 4C4 + 4C3 + 4C2 + 4C1 = 15

I used the following recursive method:

private void countAllCombinations (String input,int idx, String[] options) {

    for(int i = idx ; i < options.length; i++) {

        String output = input + "_" + options[i];

        System.out.println(output);

        countAllCombinations(output,++idx, options);

    }

}

public static void main(String[] args) {

    String arr[] = {"A","B","C","D"};

    for (int i=0;i<arr.length;i++) {

        countAllCombinations(arr[i], i, arr);

    }

}

Is there a more efficient way of doing this when the array size is large?

1 Answer

0 votes
by (13.1k points)

You can try this using a generic reusable implementation:

public static <T> Stream<List<T>> combinations(T[] arr) {

    final long N = (long) Math.pow(2, arr.length);

    return StreamSupport.stream(new AbstractSpliterator<List<T>>(N, Spliterator.SIZED) {

        long i = 1;

        @Override

        public boolean tryAdvance(Consumer<? super List<T>> action) {

            if(i < N) {

                List<T> out = new ArrayList<T>(Long.bitCount(i));

                for (int bit = 0; bit < arr.length; bit++) {

                    if((i & (1<<bit)) != 0) {

                        out.add(arr[bit]);

                    }

                }

                action.accept(out);

                ++i;

                return true;

            }

            else {

                return false;

            }

        }

    }, false);

}

Want to learn Java? Check out the Java certification from intellipaat.

Related questions

Welcome to Intellipaat Community. Get your technical queries answered by top developers!

28.4k questions

29.7k answers

500 comments

94.7k users

Browse Categories

...