Generate All Possible Combinations - Java : <p>I have a list of items {a,b,c,d} and I need to generate all possible combinations when, </p>

<ul>
<li>you can select any number of items</li>
<li>the order is not important (ab = ba)</li>
<li>empty set is not considered</li>
</ul>

<p>If we take the possibilities, it should be, </p>

<pre><code>n=4, number of items
total #of combinations = 4C4 + 4C3 + 4C2 + 4C1 = 15
</code></pre>

<p>I used the following recursive method:</p>

<pre><code>private void countAllCombinations (String input,int idx, String[] options) {
    for(int i = idx ; i &lt; 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&lt;arr.length;i++) {
        countAllCombinations(arr[i], i, arr);
    }
}
</code></pre>

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