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 <= n; k++) {
        System.out.println("of size "+k);
        List<int[]> perms = generateOfSize(k, n);
        System.out.print(perms.size()+": ");
        for(int i=0; i<perms.size(); i++){
            int[] perm = perms.get(i);
            System.out.print(perms.get(i)[0]);
            for(int j=1; j < k; j++){
                System.out.print("-"+perms.get(i)[j]);
            }
            System.out.print(", ");
        }
        System.out.println();
    }
}

public static List<int[]> generateOfSize(int k, int n){
    int[] cur = new int[k];
    List<int[]> all = new ArrayList<int[]>();

    // 1-st step - init
    for (int i = 0; i < 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] < n-1){
        cur[k-1] = cur[k-1] + 1;
        return true;
    }
    for(int i = k-1; i > 0; i--){
        if (cur[i] - cur[i-1] > 1) {
            cur[i-1] = cur[i-1] + 1;
            for (int j = i; j < 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 <= N; ++n) {
            int[] combination = IntStream.range(0, n).toArray();
            System.out.println("Combination size: " + n);
            int lineNumber = 1;

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

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

        for (int i = combination.length - 2; i >= 0; --i) {
            if (combination[i] < combination[i + 1] - 1) {
                combination[i]++;

                for (int j = i + 1; j < 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.

This is a pretty cool, efficient algorithm to generate permutations.
I have just a few tips on technique.

Simplifications

Instead of this:

int[] copy = new int[k];
System.arraycopy( cur, 0, copy, 0, cur.length );
all.add(copy);

You can simply write:

all.add(cur.clone());

---

Instead of this:

cur[k-1] = cur[k-1] + 1;

You can simplify with ++:

cur[k-1]++;

---

Instead of this:

int[] perm = perms.get(i);
System.out.print(perms.get(i)[0]);
for(int j=1; j < k; j++){
    System.out.print("-"+perms.get(i)[j]);

Why not simply reuse perm?

int[] perm = perms.get(i);
System.out.print(perm[0]);
for(int j=1; j < k; j++){
    System.out.print("-"+perm[j]);

Method decomposition

This code within generateOfSize would be better to move into its own method:

int[] cur = new int[k];

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

Or if you can use Java8, then you can use IntStream.range(0, n).toArray(); as in @Coderodde’s answer.

The code inside main could be moved in its own method too.

Naming

Your method and variable names could be improved. Some ideas:

• doShift -> shiftCombination
• cur -> combination

Formatting

The formatting is too compact. Add some spaces around operators. For example the main method becomes much more readable when auto-reformatted with an IDE like IntelliJ or Eclipse, like this:

public static void main(String[] args) {
    int n = 3;

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