Given an array arr[] of integers of size N that might contain duplicates, the task is to find all possible unique subsets.
Note: Each subset should be sorted.
Example 1:
Input: N = 3, arr[] = {2,1,2}
Output:(),(1),(1 2),(1 2 2),(2),(2 2)
Explanation: 
All possible subsets = (),(2),(1),(1,2),(2),(2,2),(2,1),(2,1,2)
After Sorting each subset = (),(2),(1),(1,2),(2),(2,2),(1,2),(1,2,2) 
Unique Susbsets in Lexicographical order = (),(1),(1,2),(1,2,2),(2),(2,2)
Example 2:
Input: N = 4, arr[] = {1,2,3,3}
Output: (),(1),(1 2),(1 2 3)
(1 2 3 3),(1 3),(1 3 3),(2),(2 3)
(2 3 3),(3),(3 3)
Your Task:
Your task is to complete the function AllSubsets() which takes the array arr[] and N as input parameters and returns list of all possible unique subsets in lexicographical order. 
Expected Time Complexity: O(2^{N}).
Expected Auxiliary Space: O(2^{N} * X), X = Length of each subset.
Constraints:
1 ≤ N ≤ 12
1 ≤ arr[i] ≤ 9

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Mathematics

Complete search

Starter code: #User function Template for python3



class Solution:

    

    #Function to find all possible unique subsets.

    def AllSubsets(self, arr,n):

        #code here

Solutions:
class Solution:

	def solve(self, s, ou, res):
		if len(s) == 0:
			res.add(tuple(ou))
			return
		ou1 = ou[:]
		ou2 = ou[:]
		ou2.append(s[0])
		s = s[1:]
		self.solve(s, ou1, res)
		self.solve(s, ou2, res)

	def AllSubsets(self, arr, n):
		ou = []
		res = set()
		arr.sort()
		self.solve(arr, ou, res)
		res = list(res)
		res.sort()
		return res


class Solution:

	def AllSubsets(self, arr, n):
		dic = {}
		arr.sort()
		self.solve(arr, (), dic)
		return sorted(dic.keys())

	def solve(self, ip, op, dic):
		if len(ip) == 0:
			if op not in dic:
				dic[op] = 1
			return
		else:
			op1 = op + (ip[0],)
			op2 = op
			ip = self.erase(ip)
			self.solve(ip, op1, dic)
			self.solve(ip, op2, dic)
			return

	def erase(self, ip):
		if len(ip) <= 1:
			return ''
		else:
			return ip[1:]


class Solution:

	def subsetsHelper(self, arr, i, n, cur, res):
		if i >= n:
			res.append(cur[:])
			return
		curInd = i + 1
		while curInd < n and arr[curInd] == arr[i]:
			curInd += 1
		count = curInd - i
		for j in range(0, count + 1):
			for k in range(j):
				cur.append(arr[i])
			self.subsetsHelper(arr, curInd, n, cur, res)
			for k in range(j):
				cur.pop()

	def AllSubsets(self, arr, n):
		res = []
		cur = []
		arr.sort()
		self.subsetsHelper(arr, 0, n, cur, res)
		res.sort()
		return res


class Solution:

	def AllSubsets(self, arr, n):

		def backtrack(start=0, cur=[]):
			result.append(cur)
			if start >= len(arr):
				return
			for i in range(start, len(arr)):
				if i > start and arr[i - 1] == arr[i]:
					continue
				backtrack(i + 1, cur + [arr[i]])
		result = []
		arr.sort()
		backtrack()
		return result


class Solution:

	def AllSubsets(self, arr, n):
		dic = {}

		def subs(idx, arr, lst, tmp):
			if idx >= len(arr):
				if str(tmp) not in dic:
					lst.append(tmp[:])
					dic[str(tmp)] = 1
				return
			tmp.append(arr[idx])
			subs(idx + 1, arr, lst, tmp)
			tmp.pop()
			subs(idx + 1, arr, lst, tmp)
		lst = []
		tmp = []
		arr.sort()
		subs(0, arr, lst, tmp)
		return sorted(lst)


from copy import deepcopy

class Solution:

	def __init__(self):
		self.ans = list()

	def AllSubsets(self, arr, n):
		ans = []
		arr = sorted(arr)

		def generate(i, sub):
			if i == n:
				ans.append(sub[:])
				return
			sub.append(arr[i])
			generate(i + 1, sub)
			sub.pop()
			while i + 1 < n and arr[i] == arr[i + 1]:
				i += 1
			generate(i + 1, sub)
		generate(0, [])
		ans = sorted(ans)
		return ans


class Solution:

	def solve(self, index, nums, op, res):
		if index >= len(nums):
			res.add(tuple(op))
			return
		op.append(nums[index])
		self.solve(index + 1, nums, op, res)
		op.pop()
		self.solve(index + 1, nums, op, res)
		return

	def AllSubsets(self, arr, n):
		arr.sort()
		op = []
		res = set()
		self.solve(0, arr, op, res)
		res = list(res)
		res.sort()
		return res


class Solution:

	def AllSubsets(self, nums, n):

		def find(cur, nums):
			result.append(cur)
			for i in range(len(nums)):
				if not i or nums[i] != nums[i - 1]:
					find(cur + [nums[i]], nums[i + 1:])
		nums.sort()
		result = []
		find([], nums)
		return result


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		subsets = []
		self.util(arr, 0, n, '', subsets)
		subsets.sort()
		res = []
		for (i, s) in enumerate(subsets):
			if i == 0:
				res.append([])
			elif i > 0 and subsets[i] != subsets[i - 1]:
				li = s.split(',')
				res.append(list(map(int, li)))
		return res

	def util(self, arr, i, n, sub, subsets):
		if i == n:
			subsets.append(sub)
			return
		if sub == '':
			s_cpy = str(arr[i])
		else:
			s_cpy = sub + ',' + str(arr[i])
		self.util(arr, i + 1, n, s_cpy, subsets)
		self.util(arr, i + 1, n, sub, subsets)


def rec(arr, res, i, ans):
	if i == len(arr):
		ans.add(tuple(res))
		return
	rec(arr, res, i + 1, ans)
	res.append(arr[i])
	rec(arr, res, i + 1, ans)
	res.pop()

class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		ans = set()
		rec(arr, [], 0, ans)
		l = list(ans)
		l.sort()
		return l


class Solution:

	def solve(self, arr, out, i, ans):
		if i >= len(arr):
			ans.add(tuple(out.copy()))
			return
		ele = arr[i]
		out.append(ele)
		self.solve(arr, out, i + 1, ans)
		out.pop()
		self.solve(arr, out, i + 1, ans)

	def AllSubsets(self, arr, n):
		arr.sort()
		ans = {()}
		i = 0
		self.solve(arr, [], i, ans)
		ans = list(ans)
		ans = list(map(list, ans))
		ans.sort()
		return ans


class Solution:

	def util(self, arr, n, res, ans):
		if n == 0:
			res.add(tuple(sorted(ans.copy())))
			return
		self.util(arr, n - 1, res, ans + [arr[n - 1]])
		self.util(arr, n - 1, res, ans)

	def AllSubsets(self, arr, n):
		res = set()
		self.util(arr, n, res, [])
		val = list()
		for x in res:
			val.append(x)
		val = sorted(val)
		return val


class Solution:

	def AllSubsets(self, arr, n):
		ans = set()

		def fun(ip, op):
			if len(ip) == 0:
				ans.add(tuple(op))
				return
			op.append(ip[0])
			fun(ip[1:], op)
			op.pop()
			fun(ip[1:], op)
		arr.sort()
		fun(arr, [])
		ans = list(map(list, ans))
		ans.sort()
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		ans = {()}
		arr.sort()

		def subset(arr, index, n, temp):
			if index >= n:
				ans.add(tuple(temp.copy()))
				return
			else:
				temp.append(arr[index])
				subset(arr, index + 1, n, temp)
				temp.pop()
				subset(arr, index + 1, n, temp)
				return
		subset(arr, 0, n, [])
		ans = list(ans)
		ans = list(map(list, ans))
		ans.sort()
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		mp = {()}
		arr.sort()

		def find(index, ds, arr, mp):
			if index >= n:
				mp.add(tuple(ds.copy()))
				return
			else:
				ds.append(arr[index])
				find(index + 1, ds.copy(), arr, mp)
				ds.pop()
				find(index + 1, ds.copy(), arr, mp)
				return
		ds = []
		find(0, ds, arr, mp)
		mp = list(mp)
		mp = list(map(list, mp))
		mp.sort()
		return mp


def subse(arr, ind, ans, res, n):
	if ind >= n:
		res.add(tuple(ans))
		return
	subse(arr, ind + 1, ans.copy(), res, n)
	ans.append(arr[ind])
	subse(arr, ind + 1, ans.copy(), res, n)

class Solution:

	def AllSubsets(self, arr, n):
		ans = []
		res = set()
		arr.sort()
		subse(arr, 0, ans, res, n)
		res = list(res)
		res.sort()
		return res


class Solution:

	def AllSubsets(self, arr, n):

		def dfs(s):
			nonlocal temp
			if s == []:
				return
			for i in range(len(s)):
				temp += s[i]
				if temp not in res:
					res.add(temp)
				dfs(s[i + 1:])
				temp = temp[:-1]
		temp = ''
		res = set()
		dfs(''.join(sorted(list(map(str, arr)))))
		res = list(res)
		ans = [[]]
		for i in range(len(res)):
			lst = []
			lst[0:] = res[i]
			ans.append(list(map(int, lst)))
		return sorted(ans)


class Solution:

	def AllSubsets(self, arr, n):

		def func(arr, li, res, n, ind, ss):
			if ind == n:
				tt = tuple(li)
				if tt not in ss:
					res.append(li.copy())
					ss.add(tt)
				return
			li.append(arr[ind])
			func(arr, li, res, n, ind + 1, ss)
			li.pop()
			func(arr, li, res, n, ind + 1, ss)
		arr.sort()
		li = []
		res = []
		ss = set()
		func(arr, li, res, n, 0, ss)
		return sorted(res)


class Solution:

	def AllSubsets(self, arr, n):
		arr = sorted(arr)

		def util(currentList, resultSet, currentIndex):
			resultSet.add(tuple(currentList))
			if currentIndex < len(arr):
				resultSet = util(currentList, resultSet, currentIndex + 1)
				nextList = currentList + [arr[currentIndex]]
				resultSet.add(tuple(nextList))
				resultSet = util(nextList, resultSet, currentIndex + 1)
			return resultSet
		return sorted(list(util([], set(), 0)))


def solve(arr, index, output, ans):
	if index >= len(arr):
		ans.append(output[:])
		return
	output.append(arr[index])
	solve(arr, index + 1, output, ans)
	output.remove(arr[index])
	while index + 1 < len(arr) and arr[index] == arr[index + 1]:
		index += 1
	solve(arr, index + 1, output, ans)

def subset(arr):
	ans = []
	output = []
	index = 0
	solve(arr, index, output, ans)
	ans.sort()
	return ans

class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		return subset(arr)


class Solution:

	def AllSubsets(self, arr, n):
		ls = {()}
		tot = n
		temp = sorted(arr)

		def sol(subs, k, temp, tot):
			if k == tot:
				ls.add(tuple(subs.copy()))
				return
			idx = k + 1
			while idx < tot and temp[idx] == temp[k]:
				idx += 1
			count = idx - k
			for j in range(count + 1):
				for i in range(j):
					subs.append(temp[k])
				sol(subs, idx, temp, tot)
				for i in range(j):
					subs.pop()
		subs = []
		sol(subs, 0, temp, tot)
		ls = list(ls)
		ls = list(map(list, ls))
		ls.sort()
		return ls


from itertools import chain, combinations

def powerset(iterable):
	s = list(iterable)
	return chain.from_iterable((combinations(s, r) for r in range(len(s) + 1)))

class Solution:

	def AllSubsets(self, arr, n):
		return sorted(set(powerset(sorted(arr))))


class Solution:

	def AllSubsets(self, nums, n):

		def backtrack(first=0, curr=[]):
			if len(curr) <= len(nums):
				output.append(list(curr))
			for i in range(first, len(nums)):
				if i > first and nums[i] == nums[i - 1]:
					continue
				curr.append(nums[i])
				backtrack(i + 1, curr)
				curr.pop()
		nums.sort()
		output = []
		backtrack()
		return output


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		subsets = []
		subsets.append([])
		(start, end) = (0, 0)
		for i in range(n):
			start = 0
			if i > 0 and arr[i] == arr[i - 1]:
				start = end + 1
			end = len(subsets) - 1
			for j in range(start, end + 1):
				newSet = list(subsets[j])
				newSet.append(arr[i])
				subsets.append(newSet)
		subsets.sort()
		return subsets


class Solution:

	def AllSubsets(self, arr, n):
		arr = sorted(arr)
		res = []

		def solve(i, subset):
			if i >= len(arr):
				res.append(subset)
				return
			sub1 = subset[:]
			subset.append(arr[i])
			solve(i + 1, subset)
			while i + 1 < len(arr) and arr[i] == arr[i + 1]:
				i += 1
			solve(i + 1, sub1)
		solve(0, [])
		return sorted(res)


class Solution:

	def AllSubsets(self, arr, n):
		if not arr:
			return
		res = []
		arr.sort()
		self.dfs(arr, 0, res, [])
		return res

	def dfs(self, arr, index, res, path):
		res.append(path)
		if index == len(arr):
			return
		for i in range(index, len(arr)):
			if i > index and arr[i] == arr[i - 1]:
				continue
			self.dfs(arr, i + 1, res, path + [arr[i]])


class Solution:

	def AllSubsets(self, arr, n):
		arr = sorted(arr)
		ans = []

		def solve(arr, n, idx, curr, ans):
			if idx >= n:
				ans.append(curr[:])
				return
			curr.append(arr[idx])
			solve(arr, n, idx + 1, curr, ans)
			curr.pop()
			while idx < n - 1 and arr[idx] == arr[idx + 1]:
				idx += 1
			solve(arr, n, idx + 1, curr, ans)
			return
		solve(arr, n, 0, [], ans)
		return sorted(ans)


def solve(arr, i, ans, temp):
	if i >= len(arr):
		ans.append(sorted(temp))
		return
	temp.append(arr[i])
	solve(arr, i + 1, ans, temp)
	temp.pop()
	solve(arr, i + 1, ans, temp)

class Solution:

	def AllSubsets(self, arr, n):
		ans = []
		solve(arr, 0, ans, [])
		f = {}
		for i in ans:
			f[tuple(i)] = 1
		l = sorted(list(f.keys()))
		return l


class Solution:

	def AllSubsets(self, nums, n):
		arr = {}
		self.subset(arr, [], 0, nums)
		temp = arr.keys()
		return sorted(temp)

	def subset(self, arr, temp, start, nums):
		if start == len(nums):
			tempo = sorted(temp)
			if tuple(tempo) not in arr:
				arr[tuple(tempo)] = 1
			return
		temp.append(nums[start])
		self.subset(arr, temp, start + 1, nums)
		temp.pop()
		self.subset(arr, temp, start + 1, nums)


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		res = [tuple()]
		for i in arr:
			temp = [tuple()]
			for j in res:
				temp.append(j)
				temp.append(j + (i,))
			res = temp
		res = set(res)
		res = list(res)
		res.sort()
		return res


class Solution:

	def AllSubsets(self, arr, n):

		def solve(ip, op, res):
			if len(ip) == 0:
				op = tuple(op)
				res.add(op)
				return
			op1 = op[:]
			op2 = op[:]
			op2.append(ip[0])
			ip.remove(ip[0])
			solve(ip[:], op1, res)
			solve(ip[:], op2, res)
		res = set()
		ip = arr[:]
		ip.sort()
		solve(ip, [], res)
		res = list(res)
		for i in range(len(res)):
			res[i] = list(res[i])
		return sorted(res)


class Solution:

	def AllSubsets(self, arr, n):
		res = set()

		def solve(arr, i, q):
			if i >= len(arr):
				q.sort()
				q = tuple(q)
				res.add(q)
				return
			solve(arr, i + 1, q[:])
			q.append(arr[i])
			solve(arr, i + 1, q[:])
		k = []
		solve(arr, 0, k)
		res = list(res)
		for i in range(len(res)):
			res[i] = list(res[i])
		return sorted(res)


class Solution:

	def AllSubsets(self, a, n):
		a.sort()
		(l, d) = ([], {})

		def backtrack(i, b, f):
			if i == n:
				if f:
					if not d.get(tuple(b), False):
						l.append(b[:])
						d[tuple(b)] = True
				return
			if f:
				if not d.get(tuple(b), False):
					l.append(b[:])
					d[tuple(b)] = True
			b.append(a[i])
			backtrack(i + 1, b, True)
			b.pop(-1)
			backtrack(i + 1, b, False)
		backtrack(0, [], True)
		return l


class Solution:

	def solve(self, inp, out, res):
		if len(inp) == 0:
			res.add(tuple(out))
			return
		out2 = out.copy()
		out2.append(inp[0])
		inp = inp[1:]
		self.solve(inp, out, res)
		self.solve(inp, out2, res)

	def AllSubsets(self, arr, n):
		subset = set()
		arr.sort()
		op = []
		self.solve(arr, op, subset)
		return sorted(list(subset))


class Solution:

	def AllSubsets(self, arr, n):

		def sol(arr, idx, n, result, ans):
			if idx == n:
				ans.append(sorted(result))
				return
			sol(arr, idx + 1, n, result, ans)
			result.append(arr[idx])
			sol(arr, idx + 1, n, result, ans)
			result.pop()
			return
		(ans, result) = ([], [])
		sol(arr, 0, n, result, ans)
		ans = set((tuple(ele) for ele in ans))
		ans = list(ans)
		return sorted(ans)


class Solution:

	def AllSubsets(self, arr, n):
		ans = set()
		arr.sort()

		def helper(idx, arr, n, ans, data):
			if idx >= n:
				ans.add(tuple(data[:]))
				return
			else:
				data.append(arr[idx])
				helper(idx + 1, arr, n, ans, data)
				data.pop()
				helper(idx + 1, arr, n, ans, data)
				return
		data = []
		helper(0, arr, n, ans, data)
		ans = list(ans)
		ans = list(map(list, ans))
		ans.sort()
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		op = []
		arr.sort()
		n = len(arr)
		res = {()}
		self.solve(arr, op, 0, n, res)
		res = list(res)
		res = list(map(list, res))
		res.sort()
		return res

	def solve(self, arr, op, i, n, res):
		if i == n:
			res.add(tuple(op))
			return
		op1 = op
		op2 = op
		self.solve(arr, op1, i + 1, n, res)
		self.solve(arr, op2 + [arr[i]], i + 1, n, res)


class Solution:

	def AllSubsets(self, arr, n):
		res = []
		dp = {}

		def recurse(arr1, k1):
			key = arr1[:]
			key.sort()
			if tuple(key) in dp:
				return
			res.append(key)
			dp[tuple(key)] = 1
			if k1 >= len(arr):
				return
			for i in range(k1, len(arr)):
				arr1.append(arr[i])
				recurse(arr1, i + 1)
				arr1.pop()
		recurse([], 0)
		res.sort()
		return res


class Solution:

	def AllSubsets(self, A, n):
		ans = set()

		def rec(tem, A, ind, n):
			if ind == n:
				ans.add(tuple(sorted(tem)))
				return
			tem.append(A[ind])
			rec(tem, A, ind + 1, n)
			tem.pop(-1)
			rec(tem, A, ind + 1, n)
		rec([], A, 0, len(A))
		ans = list(ans)
		ans.sort()
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		s = {()}
		arr.sort()

		def fun(i, arr, l):
			if i == len(arr):
				s.add(tuple(l.copy()))
				return
			l.append(arr[i])
			fun(i + 1, arr, l)
			l.pop()
			fun(i + 1, arr, l)
		fun(0, arr, [])
		a = list(s)
		a.sort()
		return a
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		n = int(input())
		a = list(map(int, input().strip().split()))
		obj = Solution()
		result = obj.AllSubsets(a, n)
		for i in range(len(result)):
			print('(', end='')
			size = len(result[i])
			for j in range(size - 1):
				print(result[i][j], end=' ')
			if size:
				print(result[i][size - 1], end=')')
			else:
				print(')', end='')
		print()


class Solution:

	def AllSubsets(self, arr, n):
		res = []
		m = {}
		arr.sort()

		def backtrack(ind, curr):
			if ind == len(arr):
				l = tuple(curr)
				if l not in m:
					m[l] = 1
					res.append(l)
				return
			backtrack(ind + 1, curr)
			curr.append(arr[ind])
			backtrack(ind + 1, curr)
			curr.pop()
		backtrack(0, [])
		res.sort()
		return res


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		b = []
		m = {}

		def rec(i, l):
			if i == n:
				e = tuple(l)
				if e not in m:
					m[e] = 1
					b.append(e)
				return
			rec(i + 1, l[:])
			rec(i + 1, l[:] + [arr[i]])
		rec(0, [])
		b.sort()
		return b


class Solution:

	def AllSubsets(self, array, n):
		array.sort()
		self.result = list()
		i = 0
		temps = list()
		self.solve(i, temps, array, n)
		return self.result

	def solve(self, i, temps, array, n):
		self.result.append(temps)
		flag = None
		for i in range(i, n):
			if flag == None or array[i] != flag:
				flag = array[i]
				self.solve(i + 1, temps + [flag], array, n)
		return None


class Solution:

	def AllSubsets(self, arr, n):
		res = []
		subset = []
		arr.sort()

		def helper(i):
			if i >= n:
				res.append(subset[:])
				return
			subset.append(arr[i])
			helper(i + 1)
			while i + 1 < n and arr[i] == arr[i + 1]:
				i += 1
			subset.pop()
			helper(i + 1)
		helper(0)
		res.sort()
		return res


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		res = []

		def solve(idx, ans):
			res.append(ans.copy())
			prev = -1
			for i in range(idx, n):
				if arr[i] != prev:
					ans.append(arr[i])
					solve(i + 1, ans)
					ans.pop()
					prev = arr[i]
		solve(0, [])
		return res


class Solution:

	def AllSubsets(self, arr, n):

		def backtrack(first, curr):
			if tuple(curr) not in tracker:
				output.append(curr[:])
				tracker[tuple(curr)] = 1
			for i in range(first, n):
				curr.append(arr[i])
				backtrack(i + 1, curr)
				curr.pop()
		arr.sort()
		tracker = {}
		output = []
		backtrack(0, [])
		return output


class Solution:

	def helper(self, ind, arr, path, ans):
		ans.append(list(path))
		for i in range(ind, len(arr)):
			if i != ind and arr[i] == arr[i - 1]:
				continue
			path.append(arr[i])
			self.helper(i + 1, arr, path, ans)
			path.pop()

	def AllSubsets(self, arr, n):
		ans = []
		arr.sort()
		self.helper(0, arr, [], ans)
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		arr = sorted(arr)

		def getSubset(index, temp, result):
			result.append(list(temp))
			if index == len(arr):
				return
			for i in range(index, len(arr)):
				if i != index and arr[i] == arr[i - 1]:
					continue
				temp.append(arr[i])
				getSubset(i + 1, temp, result)
				del temp[-1]
		result = []
		getSubset(0, [], result)
		return result


class Solution:

	def AllSubsets(self, nums, n):
		res = []
		nums.sort()
		self.rec(nums, 0, [], res)
		return res

	def rec(self, nums, idx, temp, res):
		res.append(temp[:])
		last_num = -1
		for i in range(idx, len(nums)):
			if last_num == nums[i]:
				continue
			else:
				last_num = nums[i]
				temp.append(last_num)
				self.rec(nums, i + 1, temp, res)
				temp.pop()


class Solution:

	def AllSubsets(self, arr, n):
		res = []
		arr.sort()
		self.rec(arr, 0, [], res)
		return res

	def rec(self, arr, indx, cur_arr, res):
		res.append(cur_arr[:])
		last_num = -1
		for i in range(indx, len(arr)):
			if last_num == arr[i]:
				continue
			else:
				last_num = arr[i]
				cur_arr.append(last_num)
				self.rec(arr, i + 1, cur_arr, res)
				cur_arr.pop()


class Solution:

	def AllSubsets(self, arr, n):

		def f(i, n, arr, l, ans):
			if i == n:
				ans.add(tuple(l))
				return
			f(i + 1, n, arr, l, ans)
			f(i + 1, n, arr, l + [arr[i]], ans)
			return
		arr = sorted(arr)
		ans = set()
		f(0, n, arr, [], ans)
		return sorted(list(ans))


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		res = []
		V = set()

		def bt(path, i):
			if tuple(path) not in V:
				res.append(list(path))
				V.add(tuple(path))
			for j in range(i, n):
				path.append(arr[j])
				bt(path, j + 1)
				path.pop()
		bt([], 0)
		return res


class Solution:

	def AllSubsets(self, arr, n):

		def dfs(ind, path):
			if ind == n:
				res.add(path)
				return
			dfs(ind + 1, path + (arr[ind],))
			dfs(ind + 1, path)
		res = set()
		x = tuple()
		arr.sort()
		dfs(0, x)
		res = sorted(list(res))
		return res


class Solution:

	def solve(self, arr, n, temp=(), ptr=0):
		if temp not in self.already_added:
			self.already_added.add(temp)
			self.result.append(temp)
		for i in range(ptr, n):
			self.solve(arr, n, temp + (arr[i],), i + 1)

	def __init__(self):
		self.result = []
		self.already_added = set()

	def AllSubsets(self, arr, n):
		arr.sort()
		self.solve(arr, n)
		return self.result


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		(curSet, subsets) = ([], [])
		self.helper(0, arr, n, curSet, subsets)
		subsets.sort()
		return subsets

	def helper(self, i, arr, n, curSet, subsets):
		if i >= n:
			subsets.append(curSet.copy())
			return
		curSet.append(arr[i])
		self.helper(i + 1, arr, n, curSet, subsets)
		curSet.pop()
		while i + 1 < n and arr[i] == arr[i + 1]:
			i += 1
		self.helper(i + 1, arr, n, curSet, subsets)


class Solution:

	def AllSubsets(self, arr, n):
		ans = []
		ans_set = set()
		ans.append(())
		idx = 0
		cur_subset = []
		self.allSubsetsUtil(arr, n, idx, cur_subset, ans, ans_set)
		ans.sort()
		return ans

	def allSubsetsUtil(self, arr, n, idx, cur_subset, ans, ans_set):
		for i in range(idx, n):
			cur_subset.append(arr[i])
			to_be_inserted = sorted(cur_subset)
			tup = tuple(to_be_inserted)
			if tup not in ans_set:
				ans.append(tup)
				ans_set.add(tup)
			self.allSubsetsUtil(arr, n, i + 1, cur_subset, ans, ans_set)
			cur_subset.pop()


class Solution:

	def subset(self, arr, i, curr, ans):
		if i == len(arr):
			ans.append(curr)
			return
		self.subset(arr, i + 1, curr + arr[i], ans)
		self.subset(arr, i + 1, curr, ans)

	def AllSubsets(self, arr, n):
		arr.sort()
		a = ''
		for i in arr:
			a = a + str(i)
		ans = []
		self.subset(a, 0, '', ans)
		val = set(ans)
		v2 = list(val)
		v2.sort()
		return v2


class Solution:

	def myFunc(self, ind, l, ans, arr):
		ans.append(list(l))
		for i in range(ind, len(arr)):
			if i != ind and arr[i] == arr[i - 1]:
				continue
			l.append(arr[i])
			self.myFunc(i + 1, l, ans, arr)
			l.pop(len(l) - 1)

	def AllSubsets(self, arr, n):
		l = []
		ans = []
		arr = sorted(arr)
		self.myFunc(0, l, ans, arr)
		return ans


class Solution:

	def solve(self, arr, n, idx, output, ans):
		if idx == n:
			ans.append(output)
			return
		self.solve(arr, n, idx + 1, output, ans)
		self.solve(arr, n, idx + 1, output + [arr[idx]], ans)

	def AllSubsets(self, arr, n):
		arr.sort()
		ans = []
		output = []
		brr = []
		idx = 0
		self.solve(arr, n, idx, output, ans)
		ans.sort()
		brr.append(ans[0])
		for i in range(len(ans)):
			if ans[i] != brr[-1]:
				brr.append(ans[i])
		return brr


class Solution:

	def rec(self, arr, n, i, sets, curr_set):
		sets.add(tuple(curr_set.copy()))
		for j in range(i, n):
			curr_set.append(arr[j])
			self.rec(arr, n, j + 1, sets, curr_set)
			curr_set.pop()

	def AllSubsets(self, arr, n):
		arr.sort()
		sets = set()
		self.rec(arr, n, 0, sets, [])
		new_sets = [list(i) for i in sets]
		new_sets.sort()
		return new_sets


class Solution:

	def AllSubsets(self, array, n):
		array.sort()
		result = []

		def solve(idx, cur):
			if idx == len(array):
				result.append(cur[:])
				return
			else:
				cur.append(array[idx])
				solve(idx + 1, cur)
				cur.pop()
				while idx < len(array) - 1 and array[idx] == array[idx + 1]:
					idx += 1
				solve(idx + 1, cur)
		solve(0, [])
		result.sort()
		return result


class Solution:

	def AllSubsets(self, arr, n):

		def backtrack(start, end, tmp):
			ans.append(tmp[:])
			for i in range(start, end):
				if i > start and arr[i] == arr[i - 1]:
					continue
				tmp.append(arr[i])
				backtrack(i + 1, end, tmp)
				tmp.pop()
		ans = []
		arr.sort()
		backtrack(0, len(arr), [])
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		res = []

		def solve(i, ans):
			if i == n:
				res.append(ans.copy())
				return
			ans.append(arr[i])
			solve(i + 1, ans)
			ans.pop()
			solve(i + 1, ans)
		arr.sort()
		solve(0, [])
		s = set()
		for item in res:
			s.add(tuple(item))
		ans = list(s)
		ans.sort()
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		res = []
		subset = []
		arr.sort()

		def dfs(i):
			if i >= n:
				res.append(subset.copy())
				return
			subset.append(arr[i])
			dfs(i + 1)
			subset.pop()
			dfs(i + 1)
		dfs(0)
		ctr = 1
		new = []
		res.sort()
		for i in res:
			if len(new) == 0:
				new.append(i)
			elif new[-1] != i:
				new.append(i)
		return new


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		ans = []

		def recursion(ind, ds):
			ans.append(ds.copy())
			for i in range(ind, n):
				if i > ind and arr[i] == arr[i - 1]:
					continue
				ds.append(arr[i])
				recursion(i + 1, ds)
				ds.pop()
		recursion(0, [])
		return ans


class Solution:

	def AllSubsets(self, arr, n):
		arr.sort()
		res = []

		def recur(arr, start, path):
			res.append(path.copy())
			for i in range(start, len(arr)):
				if i > start and arr[i - 1] == arr[i]:
					continue
				path.append(arr[i])
				recur(arr, i + 1, path)
				path.pop()
		recur(arr, 0, [])
		return res