Problem: Subsets 

Given an array of integers that might contain duplicates, return all possible subsets.

Note Output:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
The subsets must be sorted lexicographically.

Example :
If S = [1,2,2], the solution is:

[
[],
[1],
[1,2],
[1,2,2],
[2],
[2, 2]
]

Input:
First is T , no of test cases. 1<=T<=500
Every test case has two lines.
First line is N, size of array. 1<=N<=12
Second line contains N space seperated integers(x). 1<=x<=9.

Output:
One line per test case, every subset enclosed in () and in every set intergers should be space seperated.(See example)

Example:
Input:
2
3
1 2 2
4
1 2 3 3

Output:
()(1)(1 2)(1 2 2)(2)(2 2)
()(1)(1 2)(1 2 3)(1 2 3 3)(1 3)(1 3 3)(2)(2 3)(2 3 3)(3)(3 3)

Implementation: Python 3.x, using itertools module

from __future__ import print_function
from itertools import *
if __name__ == '__main__':
    t = input()
    for _ in range(t):
        n = input()
        l = sorted(map(int, raw_input().split()))
        length = len(l)
        res = []
        for __ in range(0, length+1):
            res.extend(list(set(combinations(l, __))))
        for t in sorted(res):
            length_t = len(t)
            if length_t == 0:
                print('()', end='')
            elif length_t == 1:
                print('(' + str(t[0]) + ')', end='')
            else:
                for i in range(length_t):
                    if i == 0:
                        print('(' + str(t[i]), end=' ')
                    elif i == length_t-1:
                        print(str(t[i]) + ')', end='')
                    else:
                        print(str(t[i]), end=' ')
        print(end='\n')
            

 

Advertisements