patternjavaMinor

all combinations of all sizes less than N

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

combinationsallthansizesless

Problem

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  perms = generateOfSize(k, n);
        System.out.print(perms.size()+": ");
        for(int i=0; i generateOfSize(int k, int n){
    int[] cur = new int[k];
    List all = new ArrayList();

    // 1-st step - init
    for (int i = 0; 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;
}

}

Solution

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 = 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.

Code Snippets

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: %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] < 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;
    }
}

Context

StackExchange Code Review Q#125850, answer score: 4

Revisions (0)

No revisions yet.