Find all possible combinations of array without permutations

Question

Input is an array of 'n' length.
I need all combinations inside this array stored into new array.

IN: j='{A, B, C ..}'
OUT: k='{A, B, C, AB, AC, BC, ABC ..}' 

Without repetitions, so without BA, CA etc.

Answer 1

Generic solution using a recursive CTE

Works for any number of elements and any base data type that supports the > operator.

WITH RECURSIVE t(i) AS (SELECT * FROM unnest('{A,B,C}'::text[]))  -- provide array
, cte AS (
   SELECT i::text AS combo, i, 1 AS ct
   FROM   t
  
   UNION  ALL
   SELECT cte.combo || t.i::text, t.i, ct + 1
   FROM   cte
   JOIN   t ON t.i > cte.i
   )
SELECT ARRAY (   
   SELECT combo
   FROM   cte
   ORDER  BY ct, combo
   ) AS result;

Result is an array of text in the example.

Note that you can have any number of additional non-recursive CTEs when using the RECURSIVE keyword.

More generic yet

If any of the following apply:

• Array elements are non-unique (like '{A,B,B}').
• The base data type does not support the > operator (like json).
• Array elements are very big - for better performance.

Use a row number instead of comparing elements:

WITH RECURSIVE t AS (
   SELECT i::text, row_number() OVER () AS rn
   FROM   unnest('{A,B,B}'::text[]) i         -- duplicate element!
   )
, cte AS (
   SELECT i AS combo, rn, 1 AS ct
   FROM   t
  
   UNION  ALL
   SELECT cte.combo || t.i, t.rn, ct + 1
   FROM   cte
   JOIN   t ON t.rn > cte.rn
   )
SELECT ARRAY (   
   SELECT combo
   FROM   cte
   ORDER  BY ct, combo
   ) AS result;

Or use WITH ORDINALITY in Postgres 9.4+:

• PostgreSQL unnest() with element number

Special case: generate decimal numbers

To generate decimal numbers with 5 digits along these lines:

WITH RECURSIVE t AS (
   SELECT i
   FROM   unnest('{1,2,3,4,5}'::int[]) i
   )
, cte AS (
   SELECT i AS nr, i
   FROM   t
  
   UNION  ALL
   SELECT cte.nr * 10 + t.i, t.i
   FROM   cte
   JOIN   t ON t.i > cte.i
   )
SELECT ARRAY (   
   SELECT nr
   FROM   cte
   ORDER  BY nr
   ) AS result;

SQL Fiddle demonstrating all.

Answer 2

if n is small < 20 , all possible combinations can be found using a bitmask approach. There are 2^n different combinations of it. The number values 0 to (2^n - 1) represents one of the combination. e.g n=3

0 represents {},empty element
2^3-1=7= 111 b represents element, abc

pseudo code as follows

for b=0 to 2^n - 1 do #each combination
  res=""
  for i=0 to (n-1) do   # which elements are included

     if (b && (1<<i) != 0)
        res= res+arr[i]
    end
    print res
  end
end