CODEWITHSUNDEEP
javaalgorithmbit-manipulation
Gagan Deep
Gagan Deep

Reputation: 79

find all subsets of array having subset of size greater than or equal to 2

The below code prints all subsets, but I need of size greater than or equal to 2. 

public static void printSubsets(char set[])
{
    int n = set.length;

    for (int i = 0; i < (1<<n); i++)
    {
        System.out.print("{ ");

        for (int j = 0; j < n; j++)

            if ((i & (1 << j)) >0 )
                System.out.print(set[j] + " ");

        System.out.println("}");
    }
}

Upvotes: 2

Views: 615

Answers (1)

John Kugelman
John Kugelman

Reputation: 361729

A subset of size 0 corresponds to i == 0. To eliminate the empty subset start at i = 1.

A subset of size 1 corresponds to i having exactly one bit set; or, equivalently, when it is a power of 2. A positive number i is a power of two if (i & (i - 1)) == 0.

for (int i = 1; i < (1<<n); i++) {
    if ((i & (i - 1)) == 0) {
        continue;
    }

    System.out.print("{ ");

    for (int j = 0; j < n; j++) {
        if ((i & (1 << j)) != 0) {
            System.out.print(set[j] + " ");
        }
    }

    System.out.println("}");
}

Alternatively, you could keep your original loop and simply insert this check:

if (Integer.bitCount(i) < 2) {
    continue;
}

It's not as clever or efficient, but it is nice and readable.

Upvotes: 4

Related Questions