all combinations of all sizes less than N I want to generate all possible combinations (without duplicates) of all sizes less or equal than \$N\$, so for example if \$N=3\$ I want to generate the following
\$\{1\},\{2\},\{3\},
\{1,2\},\{1,3\},\{2,3\},
\{1,2,3\}.\$

I created the following algorithm in Java. Is there a more optimal way to generate?

public class Main {

public static void main(String[] args) {

    int n = 3;

    for (int k=1; k &lt;= n; k++) {
        System.out.println("of size "+k);
        List&lt;int[]&gt; perms = generateOfSize(k, n);
        System.out.print(perms.size()+": ");
        for(int i=0; i&lt;perms.size(); i++){
            int[] perm = perms.get(i);
            System.out.print(perms.get(i)[0]);
            for(int j=1; j &lt; k; j++){
                System.out.print("-"+perms.get(i)[j]);
            }
            System.out.print(", ");
        }
        System.out.println();
    }
}

public static List&lt;int[]&gt; generateOfSize(int k, int n){
    int[] cur = new int[k];
    List&lt;int[]&gt; all = new ArrayList&lt;int[]&gt;();

    // 1-st step - init
    for (int i = 0; i &lt; k; i++){
        cur[i] = i;
    }

    // 2-nd step - do shifts
    do{
        int[] copy = new int[k];
        System.arraycopy( cur, 0, copy, 0, cur.length );
        all.add(copy);
    } while (doShift(cur, k, n));

    return all;
}

public static boolean doShift(int[] cur, int k, int n){
    if (cur[k-1] &lt; n-1){
        cur[k-1] = cur[k-1] + 1;
        return true;
    }
    for(int i = k-1; i &gt; 0; i--){
        if (cur[i] - cur[i-1] &gt; 1) {
            cur[i-1] = cur[i-1] + 1;
            for (int j = i; j &lt; k; j++){
                cur[j] = cur[j-1]+1;
            }
            return true;
        }
    }
    return false;
}

}
You can rewrite your implementation much succintly:

import java.util.Arrays;
import java.util.stream.IntStream;

public class Main {

    public static void main(String[] args) {
        final int N = 4;

        int globalLineNumber = 1;

        for (int n = 1; n &lt;= N; ++n) {
            int[] combination = IntStream.range(0, n).toArray();
            System.out.println("Combination size: " + n);
            int lineNumber = 1;

            do {
                System.out.printf("[%3d] %3d: %s\n", 
                                  globalLineNumber++,
                                  lineNumber++, 
                                  Arrays.toString(combination));
            } while ((combination = 
                      generateNextCombination(combination, N)) != null);
        }
    }

    public static int[] generateNextCombination(int[] combination, int n) {
        if (combination[combination.length - 1] &lt; n - 1) {
            combination[combination.length - 1]++;
            return combination;
        }

        for (int i = combination.length - 2; i &gt;= 0; --i) {
            if (combination[i] &lt; combination[i + 1] - 1) {
                combination[i]++;

                for (int j = i + 1; j &lt; combination.length; ++j) {
                    combination[j] = combination[j - 1] + 1;
                }

                return combination;
            }
        }

        return null;
    }
}


The above produces the following output:



Combination size: 1
[  1]   1: [0]
[  2]   2: [1]
[  3]   3: [2]
[  4]   4: [3]
Combination size: 2
[  5]   1: [0, 1]
[  6]   2: [0, 2]
[  7]   3: [0, 3]
[  8]   4: [1, 2]
[  9]   5: [1, 3]
[ 10]   6: [2, 3]
Combination size: 3
[ 11]   1: [0, 1, 2]
[ 12]   2: [0, 1, 3]
[ 13]   3: [0, 2, 3]
[ 14]   4: [1, 2, 3]
Combination size: 4
[ 15]   1: [0, 1, 2, 3]



Basically, you are given \$N\$ - the number of all possible items you can choose. Also, you are given \$n\$ - the number of \$N\$ items you actually put in a combination. Now, you have a simple class method for producing the next \$n\$-combination. Whenever all \$n\$-combinations where generated, return null in order to signal that you are done with them, after which increment \$n\$, generate the first lexicographic combination, and keep generating until null.

Hope that helps.

Addition

Of course, instead of combination and null you could return true or false depending on the case whether the input combination was successfully "incremented" towards the next combination or not.