Given a set of positive integers, find all its subsets.
Example 1 :
Input : 
array = {1, 2, 3}
Output :
// this space denotes null element. 
1
1 2
1 2 3
1 3
2
2 3
3
Explanation: 
The following are the subsets 
of the array {1, 2, 3}.
Example 2 :
Input :
array = {1, 2}
Output :
1 
1 2
2
Explanation :
The following are the 
subsets of {1, 2}.
Your task :
You don't have to read input or print anything. Your task is to complete the function subsets() which takes the array of integers as input and returns the list of list containing the subsets of the given set of numbers in lexicographical order.
 
Expected Time Complexity : O(2^n)))
Expected Auxiliary Space : O(2^n*length of each subset)
 
Constraints :
1 <= n <= 20
1 <= arr[i] <=10

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3



class Solution:

    def subsets(self, A):

        #code here

Solutions:
class Solution:

	def subsets(self, A):
		l = []
		res = []
		A = list(A)

		def subs(A, l, res):
			if len(A) == 0:
				res.append(l)
				return
			l1 = l[:]
			l2 = l[:]
			l2.append(A[0])
			subs(A[1:], l1, res)
			subs(A[1:], l2, res)
		subs(A, l, res)
		res.sort()
		return res


class Solution:

	def subsets(self, A):
		op = []
		lis = []
		self.solve(A, op, lis)
		lis.sort()
		return lis

	def solve(self, A, op, lis):
		if len(A) == 0:
			lis.append(op)
			return
		op1 = op[:]
		op2 = op[:]
		op2.append(A[0])
		A = A[1:]
		self.solve(A, op1, lis)
		self.solve(A, op2, lis)


class Solution:

	def subsets(self, A):
		ans = []
		temp = []

		def answer(i, temp):
			if i == len(A):
				ans.append(temp.copy())
				return
			temp.append(A[i])
			answer(i + 1, temp)
			temp.pop()
			answer(i + 1, temp)
		answer(0, temp)
		ans.sort()
		return ans


class Solution:

	def find(self, a, ans, tmp, index, n):
		tmp = tmp.copy()
		ans.append(tmp)
		for i in range(index, n):
			tmp.append(a[i])
			self.find(a, ans, tmp, i + 1, n)
			tmp.pop()

	def subsets(self, A):
		ans = []
		self.find(A, ans, [], 0, len(A))
		ans.sort()
		return ans


class Solution:

	def helper(self, list1, ans, ind, A):
		if ind == len(A):
			ans.append(list1.copy())
			return
		list1.append(A[ind])
		self.helper(list1, ans, ind + 1, A)
		list1.pop()
		self.helper(list1, ans, ind + 1, A)

	def subsets(self, A):
		ans = []
		list1 = []
		self.helper(list1, ans, 0, A)
		ans.sort()
		return ans


class Solution:

	def subsets(self, nums):
		res = []
		subset = []

		def dfs(i):
			if i >= len(nums):
				res.append(subset[:])
				return
			subset.append(nums[i])
			dfs(i + 1)
			subset.pop()
			dfs(i + 1)
		dfs(0)
		res.sort()
		return res


class Solution:

	def subsets(self, A):
		lst = []
		tmp = []

		def subs(idx, A, n, lst, tmp):
			if idx >= n:
				lst.append(tmp[:])
				return
			tmp.append(A[idx])
			subs(idx + 1, A, n, lst, tmp)
			tmp.pop()
			subs(idx + 1, A, n, lst, tmp)
		subs(0, A, len(A), lst, tmp)
		return sorted(lst)


class Solution:

	def solve(self, A, ans, output, index):
		if index >= len(A):
			ans.append(output[:])
			return
		self.solve(A, ans, output, index + 1)
		output.append(A[index])
		self.solve(A, ans, output, index + 1)
		output.pop()

	def subsets(self, A):
		ans = []
		output = []
		index = 0
		self.solve(A, ans, output, index)
		ans.sort()
		return ans


class Solution:

	def subsets(self, A):

		def sub(i, A, l, m):
			if i >= len(A):
				m.append(l[:])
				return
			l.append(A[i])
			sub(i + 1, A, l, m)
			l.pop()
			sub(i + 1, A, l, m)
		(i, l, m) = (0, [], [])
		sub(i, A, l, m)
		return sorted(m)


class Solution:

	def subsets(self, A):

		def helper(A, ind, temp, res):
			if ind == len(A):
				res.append(temp.copy())
				return
			temp.append(A[ind])
			helper(A, ind + 1, temp, res)
			temp.pop()
			helper(A, ind + 1, temp, res)
		res = []
		temp = []
		helper(A, 0, temp, res)
		res.sort()
		return res


class Solution:

	def subsets(self, A):

		def subs(idx, arr, N, lst, l):
			if idx >= N:
				l.append(lst[:])
				return
			lst.append(arr[idx])
			subs(idx + 1, arr, N, lst, l)
			lst.pop()
			subs(idx + 1, arr, N, lst, l)
			return
		N = len(A)
		lst = []
		l = []
		subs(0, A, N, lst, l)
		return sorted(l)


class Solution:

	def find(index, A, ds, mat):
		if index >= len(A):
			mat.append(ds)
			return
		ds.append(A[index])
		Solution.find(index + 1, A, ds.copy(), mat)
		ds.pop()
		Solution.find(index + 1, A, ds.copy(), mat)

	def subsets(self, A):
		ds = []
		mat = []
		index = 0
		Solution.find(index, A, ds.copy(), mat)
		mat.sort()
		return mat


class Solution:

	def __init__(self):
		self.ans = []

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

	def subsets(self, A):
		self.helper(A, [], 0)
		return sorted(self.ans)


class Solution:

	def subsets(self, A):
		res = []
		self.solve(A, [], 0, res)
		res.sort()
		return res

	def solve(self, A, ss, index, res):
		res.append(ss[:])
		for i in range(index, len(A)):
			ss.append(A[i])
			self.solve(A, ss, i + 1, res)
			ss.pop(-1)


class Solution:

	def subsets(self, A):
		ans = [[]]

		def backtrack(arr, curr):
			if len(arr) > 0:
				ans.append(arr[:])
			for i in range(curr, len(A)):
				arr.append(A[i])
				backtrack(arr, i + 1)
				arr.pop()
		backtrack([], 0)
		ans.sort()
		return ans


def solve(nums, ans, index, arr):
	if index == len(nums):
		ans.append(arr)
		return
	solve(nums, ans, index + 1, arr + [nums[index]])
	solve(nums, ans, index + 1, arr)

class Solution:

	def subsets(self, nums):
		ans = []
		solve(nums, ans, 0, [])
		ans.sort()
		return ans


class Solution:

	def subsets(self, A):

		def fun(i, A):
			if i == len(A):
				l1.append(l.copy())
				return
			l.append(A[i])
			fun(i + 1, A)
			l.pop()
			fun(i + 1, A)
			return
		i = 0
		l = []
		l1 = []
		fun(i, A)
		return sorted(l1)


class Solution:

	def __init__(self):
		self.ans = []
		self.cur = []

	def solve(self, arr, N, ind):
		self.ans.append(self.cur.copy())
		for i in range(ind, N):
			self.cur.append(arr[i])
			self.solve(arr, N, i + 1)
			self.cur.pop()

	def subsets(self, A):
		self.solve(A, len(A), 0)
		self.ans.sort()
		return self.ans


class Solution:

	def helper(self, A, idx, temp, Arr):
		temp_copy = temp.copy()
		if len(A) == idx:
			Arr.append(temp_copy)
			return
		temp_copy.append(A[idx])
		self.helper(A, idx + 1, temp_copy, Arr)
		temp_copy.pop()
		self.helper(A, idx + 1, temp_copy, Arr)
		return

	def subsets(self, A):
		Arr = []
		self.helper(A, 0, [], Arr)
		return sorted(Arr)


class Solution:

	def subsets(self, A):

		def helper(op, inp):
			res = []
			if not inp:
				res.append(op)
				return res
			op2 = op.copy()
			op2.append(inp[0])
			inp = inp[1:]
			res += helper(op, inp)
			res += helper(op2, inp)
			return res
		z = helper([], A)
		z.sort()
		return z


class Solution:

	def subsets(self, A):

		def find(n, temp):
			if n >= N:
				out.append(temp)
				return
			find(n + 1, temp)
			find(n + 1, temp + [A[n]])
		N = len(A)
		out = []
		find(0, [])
		return sorted(out)


class Solution:

	def AllSubsets(self, A, n, ind, lst, ans):
		if ind == n:
			ans.append(list(lst))
			return
		else:
			lst.append(A[ind])
			self.AllSubsets(A, n, ind + 1, lst, ans)
			lst.pop()
			self.AllSubsets(A, n, ind + 1, lst, ans)
		return ans

	def subsets(self, A):
		B = self.AllSubsets(A, len(A), 0, [], [])
		return sorted(B)


class Solution:

	def subsets(self, A):
		n = len(A)

		def solve(idx, l, ans):
			if idx == n:
				ans.append(l.copy())
				return
			l.append(A[idx])
			solve(idx + 1, l, ans)
			l.pop()
			solve(idx + 1, l, ans)
		ans = []
		solve(0, [], ans)
		return sorted(ans)


class Solution:

	def subsets(self, A):

		def subs(l):
			if l == []:
				return [[]]
			x = subs(l[1:])
			return x + [[l[0]] + y for y in x]
		return sorted(subs(A))


class Solution:

	def subsets(self, A):

		def solve(A, index, op):
			if index >= len(A):
				res.append(op.copy())
				return
			op.append(A[index])
			solve(A, index + 1, op)
			op.pop()
			solve(A, index + 1, op)
			return
		res = []
		op = []
		solve(A, 0, op)
		res.sort()
		return res


class Solution:

	def subsets(self, A):

		def subs(inp, out, res):
			if len(inp) == 0:
				res.append(out)
				return
			out1 = out[:]
			out2 = out[:]
			out2.append(inp[0])
			subs(inp[1:], out1, res)
			subs(inp[1:], out2, res)
			return
		res = []
		out = []
		subs(A, out, res)
		return sorted(res)


class Solution:

	def solve_iter(self, A, n, res):
		res.append([])
		for num in A:
			n = len(res)
			for j in range(n):
				res.append(res[j] + [num])

	def solve(self, arr, start, n, subset, ans):
		ans.append(subset[:])
		for i in range(start, n):
			subset.append(arr[i])
			self.solve(arr, i + 1, n, subset, ans)
			subset.pop()

	def subsets(self, A):
		n = len(A)
		res = []
		self.solve(A, 0, n, [], res)
		res.sort()
		return res


class Solution:

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

	def subsets(self, A):
		ans = []
		i = 0
		self.solve(A, [], i, ans)
		ans = list(ans)
		ans.sort()
		return ans


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

class Solution:

	def subsets(self, A):
		ans = []
		lis = []
		rec(A, 0, lis, ans)
		ans.sort()
		return ans


class Solution:

	def subsets(self, nums):

		def sub(j, curr, nums):
			res.append(curr[:])
			for i in range(j, len(nums)):
				curr.append(nums[i])
				sub(i + 1, curr, nums)
				curr.pop(len(curr) - 1)
		res = []
		sub(0, [], nums)
		res.sort()
		return res


class Solution:

	def subsets(self, A):
		if len(A) == 0:
			return [[]]
		smallOut = self.subsets(A[1:])
		smallOut1 = self.subsets(A[1:])
		for i in smallOut1:
			i.insert(0, A[0])
		sm = smallOut1 + smallOut
		sm.sort()
		return sm


class Solution:

	def subsets(self, A):
		res = []
		op = []
		self.solve(A, op, res)
		return sorted(res)

	def solve(self, ip, op, res):
		if len(ip) == 0:
			res.append(op)
			return
		op1 = op[:]
		op2 = op[:]
		op2.append(ip[0])
		self.solve(ip[1:], op1, res)
		self.solve(ip[1:], op2, res)
		return


class Solution:

	def subsets(self, A):
		res = []
		subset = []

		def dfs(i):
			if i >= len(A):
				res.append(subset.copy())
				return
			subset.append(A[i])
			dfs(i + 1)
			subset.pop()
			dfs(i + 1)
		dfs(0)
		return sorted(res)


class Solution:

	def subsets(self, A):
		ans = []

		def fn(res, i):
			if i == len(A):
				ans.append(res.copy())
				return
			fn(res + [A[i]], i + 1)
			fn(res, i + 1)
		fn([], 0)
		return sorted(ans)


class Solution:

	def subsets(self, nums):
		subsets = [[]]
		for num in nums:
			for i in range(len(subsets)):
				currSubset = subsets[i]
				subsets.append(currSubset + [num])
		return sorted(subsets)


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

class Solution:

	def subsets(self, A):
		n = len(A)
		ans = []
		res = []
		sub(A, 0, n, ans.copy(), res)
		res.sort()
		return res


class Solution:

	def subsets(self, arr):
		res = [[]]
		n = len(arr)
		for i in range(n):
			for j in range(len(res)):
				res.append(res[j] + [arr[i]])
		return sorted(res)


class Solution:

	def subsets(self, A):

		def dfs(i, path):
			if i == len(A):
				return [path]
			return dfs(i + 1, path + [A[i]]) + dfs(i + 1, path)
		ans = dfs(0, [])
		ans.sort(key=lambda x: x)
		return ans


class Solution:

	def subsets(self, A):
		res = []
		subset = []

		def bfs(i):
			if i >= len(A):
				res.append(subset.copy())
				return
			subset.append(A[i])
			bfs(i + 1)
			subset.pop()
			bfs(i + 1)
		bfs(0)
		res.sort()
		return res


class Solution:

	def subsets(self, A):

		def subset(p, A, sol):
			if len(A) == 0:
				sol.append(p)
				return
			subset(p + [A[0]], A[1:], sol)
			subset(p, A[1:], sol)
			return
		sol = []
		subset([], A, sol)
		sol.sort()
		return sol


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 subsets(self, A):
		return sorted(powerset(A))


from itertools import combinations

class Solution:

	def subsets(self, A):
		n = len(A)
		ans = [[]]
		for i in range(1, n + 1):
			for j in combinations(A, i):
				t = [i for i in j]
				ans.append(t)
		return sorted(ans)


class Solution:

	def subsets(self, A):

		def helper(i, subset, A, ans):
			if i >= len(A):
				ans.append(subset.copy())
				return
			subset.append(A[i])
			helper(i + 1, subset, A, ans)
			subset.pop()
			helper(i + 1, subset, A, ans)
		ans = []
		subset = []
		helper(0, subset, A, ans)
		return sorted(ans)


class Solution:

	def subsets(self, A):
		ans = []

		def fun(idx, lis):
			if idx == len(A):
				ans.append(lis)
				return
			new1 = lis[:]
			new2 = lis[:]
			new2.append(A[idx])
			fun(idx + 1, new2)
			fun(idx + 1, new1)
			return
		fun(0, [])
		ans.sort()
		return ans


class Solution:

	def subsets(self, A):
		n = len(A)
		result = []

		def find(s, result, start, A):
			result.append(s[:])
			for i in range(start, n, 1):
				s.append(A[i])
				find(s, result, i + 1, A)
				s.pop(-1)
		find([], result, 0, A)
		return sorted(result)


class Solution:

	def subsets(self, arr):
		subsets = []
		subsets.append([])
		for num in arr:
			n = len(subsets)
			for i in range(n):
				newSet = list(subsets[i])
				newSet.append(num)
				subsets.append(newSet)
		subsets.sort()
		return subsets


class Solution:

	def subsets(self, A):
		res = []

		def dfs(i, cur):
			if i == len(A):
				res.append(cur)
				return
			dfs(i + 1, cur)
			dfs(i + 1, cur + [A[i]])
		dfs(0, [])
		return sorted(res)


class Solution:

	def subsets(self, A):
		p = []
		for i in range(2 ** len(A)):
			a = []
			for j in range(len(A)):
				if 1 << j & i:
					a.append(A[j])
			p.append(a)
		return sorted(p)


class Solution:

	def subsets(self, A):

		def subs(inp, path, res):
			if len(inp) == 0:
				res.append(path)
				return
			subs(inp[1:], path + [inp[0]], res)
			subs(inp[1:], path, res)
			return
		res = []
		path = []
		subs(A, path, res)
		return sorted(res)


class Solution:

	def subsets(self, A):
		l1 = []
		n = len(A)
		for i in range(1 << n):
			l = []
			for j in range(n):
				if i & 1 << j:
					l.append(A[j])
			l1.append(l)
		l1.sort()
		return l1


class Solution:

	def subsets(self, arr):
		ans = []

		def siva(arr, i, ds):
			if i == len(arr):
				ans.append(ds.copy())
				return
			ds.append(arr[i])
			siva(arr, i + 1, ds)
			ds.pop()
			siva(arr, i + 1, ds)
		siva(arr, 0, [])
		return sorted(ans)


class Solution:

	def subsets(self, A):
		ans = [[]]
		for i in A:
			ans += [j + [i] for j in ans]
		return sorted(ans)


class Solution:

	def subset_rec(self, A, l, s, idx):
		self._res.append([*s])
		if idx >= l:
			return
		for i in range(idx, l):
			s.append(A[i])
			self.subset_rec(A, l, s, i + 1)
			s.pop(-1)

	def subsets(self, A):
		self._res = []
		self.subset_rec(A, len(A), [], 0)
		self._res.sort()
		return self._res


class Solution:

	def subsets(self, A):

		def subs(input, output, res):
			if len(input) == 0:
				res.append(output)
				return
			output1 = output[:]
			output2 = output[:]
			output2.append(input[0])
			subs(input[1:], output1, res)
			subs(input[1:], output2, res)
			return
		res = []
		output = []
		subs(A, output, res)
		return sorted(res)


class Solution:

	def subsets(self, a):
		l = []
		for i in range(2 ** n):
			l1 = []
			for j in range(n):
				if i & 1 << j:
					l1.append(a[j])
			l.append(l1)
		return sorted(l)


class Solution:

	def subsets(self, a):
		l = []
		for i in range(2 ** len(a)):
			x = []
			for j in range(len(a)):
				if i & 1 << j:
					x.append(a[j])
			l.append(x)
		return sorted(l)


class Solution:

	def subsets(self, A):
		res = []
		opt = []

		def solve(i):
			if i == len(A):
				res.append(opt.copy())
				return
			opt.append(A[i])
			solve(i + 1)
			opt.pop()
			solve(i + 1)
			return
		solve(0)
		res.sort()
		return res


class Solution:

	def __init__(self):
		self.ans = []

	def helper(self, A, temp, i):
		if len(A) == 0:
			self.ans.append(temp)
			return
		temp1 = temp[:]
		temp2 = temp[:]
		temp2.append(A[0])
		A = A[1:]
		self.helper(A, temp1, i + 1)
		self.helper(A, temp2, i + 1)
		return

	def subsets(self, A):
		temp = []
		self.helper(A, temp, 0)
		self.ans.sort()
		return self.ans


class Solution:

	def subsets(self, a):
		res = []
		for i in range(1 << len(a)):
			li = []
			x = bin(i)[2:].rjust(len(a), '0')
			for j in range(len(x)):
				if x[j] == '1':
					li.append(a[j])
			res.append(li)
		res.sort()
		return res


class Solution:

	def subsets(self, A):
		op = ''
		ip = []
		for i in A:
			ip = ip + [i]
		ans = []
		op = []
		arr = self.solve(ip, op, ans)
		arr.sort()
		return arr

	def solve(self, ip, op, ans):
		if len(ip) == 0:
			x = []
			x.extend(op)
			ans.append(x)
			return
		op1 = op
		op2 = op
		op2 = op2 + [ip[0]]
		self.solve(ip[1:], op1, ans)
		self.solve(ip[1:], op2, ans)
		return ans


class Solution:

	def subsets(self, A):

		def recurs(i, li, ans):
			if i < 0:
				ans.append(li[:])
				return
			else:
				recurs(i - 1, li, ans)
				recurs(i - 1, [A[i]] + li, ans)
				return
		ans = []
		recurs(len(A) - 1, [], ans)
		ans.sort()
		return ans


class Solution:

	def subseq(self, A, i, res, n, s):
		if i >= n:
			s.append(res.copy())
			return
		res.append(A[i])
		self.subseq(A, i + 1, res, n, s)
		res.pop()
		self.subseq(A, i + 1, res, n, s)
		return s

	def subsets(self, A):
		res = []
		n = len(A)
		s = []
		l = self.subseq(A, 0, res, n, s)
		l.sort()
		return l


class Solution:

	def subsets(self, A):
		k = 2 ** len(A)
		ans = [[]]
		for i in range(1, k):
			s = 0
			v = []
			for j in range(len(A)):
				if i & 1 << j:
					v.append(A[j])
			ans.append(v)
		ans.sort()
		return ans


class Solution:

	def subsetsUtil(self, A, subset, index, res, n):
		if index == n:
			return res.append([*subset])
		self.subsetsUtil(A, subset, index + 1, res, n)
		subset.append(A[index])
		self.subsetsUtil(A, subset, index + 1, res, n)
		subset.pop()

	def subsets(self, A):
		subset = []
		res = []
		k = self.subsetsUtil(A, subset, 0, res, len(A))
		res.sort()
		return res


class Solution:

	def func(self, n):
		if not n:
			return [[]]
		ans = []
		for i in self.func(n[1:]):
			ans.append(i)
			ans.append([n[0]] + i)
		return ans

	def subsets(self, A):
		return sorted(self.func(A))


class Solution:

	def subsetsUtil(self, A, subset, index, res):
		res.append([*subset])
		for i in range(index, len(A)):
			subset.append(A[i])
			self.subsetsUtil(A, subset, i + 1, res)
			subset.pop()
		return subset

	def subsets(self, A):
		global res
		subset = []
		index = 0
		res = []
		k = self.subsetsUtil(A, subset, index, res)
		res.sort()
		return res


class Solution:

	def subsets_helper(self, A, subset_arr, n, ans):
		if n == len(A):
			ans.append(subset_arr)
			return
		self.subsets_helper(A, subset_arr + [A[n]], n + 1, ans)
		self.subsets_helper(A, subset_arr, n + 1, ans)

	def subsets(self, A):
		ans = []
		self.subsets_helper(A, [], 0, ans)
		ans.sort()
		return ans


class Solution:

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


class Solution:

	def subsets(self, a):
		l = []

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


class Solution:

	def solve(self, ind, n, a, temp, res):
		if ind == n:
			res.append(temp[:])
			return
		temp.append(a[ind])
		self.solve(ind + 1, n, a, temp, res)
		temp.pop()
		self.solve(ind + 1, n, a, temp, res)

	def subsets(self, A):
		res = []
		self.solve(0, len(A), A, [], res)
		res.sort()
		return res


class Solution:

	def subsets(self, A):
		ans = []

		def solve(temp, i):
			if i == len(A):
				ans.append(temp.copy())
				return
			solve(temp + [A[i]], i + 1)
			solve(temp, i + 1)
		solve([], 0)
		return sorted(ans)


class Solution:

	def subsets(self, A):
		ip = A
		op = []
		ans = []
		self.subset2(ip, op, ans)
		return sorted(ans)

	def subset2(self, ip, op, ans):
		if len(ip) == 0:
			ans.append(op)
			return
		include = op.copy()
		exclude = op.copy()
		include.append(ip[0])
		ip = ip[1:]
		self.subset2(ip, exclude, ans)
		self.subset2(ip, include, ans)


class Solution:

	def subsets(self, A):
		n = len(A)
		ans = []
		for num in range(1 << n):
			sub = []
			for i in range(n):
				if num & 1 << i:
					sub.append(A[i])
			ans.append(sub)
		ans.sort()
		return ans


class Solution:

	def subsets(self, A):
		s1 = []
		ans = []
		i = 0
		self.sub(ans, s1, i, A)
		return sorted(ans)

	def sub(self, ans, s1, i, A):
		if i >= len(A):
			ans.append(s1.copy())
			return
		s1.append(A[i])
		self.sub(ans, s1, i + 1, A)
		s1.pop()
		self.sub(ans, s1, i + 1, A)


class Solution:

	def findAllSubset(self, ind, n, arr, ans, temp):
		if ind == n:
			ans.append(temp[:])
			return
		temp.append(arr[0])
		self.findAllSubset(ind + 1, n, arr[1:], ans, temp)
		temp.pop()
		self.findAllSubset(ind + 1, n, arr[1:], ans, temp)

	def subsets(self, arr):
		ans = []
		self.findAllSubset(0, len(arr), arr, ans, [])
		ans.sort()
		return ans


class Solution:

	def subsets(self, arr):
		n = len(arr)
		total_subs = 2 ** n
		ans = []
		for i in range(0, total_subs):
			sub = []
			for j in range(0, n):
				if i & 1 << j:
					sub.append(arr[j])
			ans.append(sub)
		ans.sort()
		return ans