Subsets generation#4106

Subsets generation (Editorial)

The task is to generate all subsets of a given set. To do this, iterate through all numbers from $1$ to $2^{n} - 1$ 2^n - 1. Represent the number $i$ in binary and consider its last $n$ bits (which may include leading zeros). Each such binary representation corresponds to a subset: if the $k$ -th bit is set to $1$ , then the number $k (1 \leq k \leq n)$ k~(1 \le k \le n) is included in the subset. For example:

if $n = 3$ n = 3 and $i = 2$ i = 2, the binary representation of $i = 01 0_{2}$ i = 010_2 corresponds to the subset ${2}$ .
if $n = 4$ n = 4 and $i = 11$ i = 11, the binary representation of $i = 101 1_{2}$ i = 1011_2 corresponds to the subset ${1, 2, 4}$ \{1, 2, 4\}.

Example

Let’s consider the generation of subsets for $n = 3$ n = 3.

Algorithm implementation

We'll generate subsets as numbers stored in the array $v$ . For example, the subset ${1, 2, 3}$ \{1, 2, 3\} will be represented as the number $123$ .

#define MAX 8
int v[1 << MAX];

Read the input value $n$ .

scanf("%d",&n);

In a loop, iterate through all possible masks for subsets of a set with $n$ elements. The operation $1 << n$ 1 << n shifts the number $1$ to the left by $n$ positions, which is equivalent to raising $2$ to the power of $n$ . Generate all $2^{n} - 1$ 2^n - 1 subsets (excluding the empty one).

for (i = 1; i < (1 << n); i++)
{

Store the elements of the current subset in the variable $x$ as a string. For example, the subset ${1, 2, 4}$ \{1, 2, 4\} will be stored as $x = 124$ x = 124.

  x = 0;
  for (j = 0; j < n; j++)
    if (i & (1 << j)) x = x * 10 + j + 1;
  v[i] = x;
}

Sort the subsets in ascending order based on their corresponding numbers.

sort(v, v + (1 << n));

Print the subsets in the required order.

for (i = 1; i < 1 << n; i++)
  printf("%d\n", v[i]);

Java implementation

import java.util.*;

public class Main
{
  public static void main(String []args)
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    int v[] = new int[1<<n];
    
    for(int i = 1; i < (1 << n); i++)
    {
      int val, j;    	
      for(val = j = 0; j < n; j++)
        if ((i & (1 << j)) > 0) val = val * 10 + j + 1;
      v[i] = val;
    }

    Arrays.sort(v);
    for(int i = 1; i < 1 << n; i++)
      System.out.println(v[i]);
    con.close();
  }
}

Java