Given an array of integers and a sum B, find all unique combinations in the array where the sum is equal to B. The same number may be chosen from the array any number of times to make B.
Note:
        1. All numbers will be positive integers.
        2. Elements in a combination (a1, a2, …, ak) must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak).
        3. The combinations themselves must be sorted in ascending order.
Example 1:
Input:
N = 4
arr[] = {7,2,6,5}
B = 16
Output:
(2 2 2 2 2 2 2 2)
(2 2 2 2 2 6)
(2 2 2 5 5)
(2 2 5 7)
(2 2 6 6)
(2 7 7)
(5 5 6)
Example 2:
Input:
N = 11
arr[] = {6,5,7,1,8,2,9,9,7,7,9}
B = 6
Output:
(1 1 1 1 1 1)
(1 1 1 1 2)
(1 1 2 2)
(1 5)
(2 2 2)
(6)
Your Task:
Your task is to complete the function combinationSum() which takes the array A and a sum B as inputs and returns a list of list denoting the required combinations in the order specified in the problem description. The printing is done by the driver's code. If no set can be formed with the given set, then  "Empty" (without quotes) is printed.
Expected Time Complexity: O(X^{2} * 2^{N}), where X is average of summation B/arr_{i }for every number in the array.
Expected Auxiliary Space: O(X * 2^{N})
Constraints:
1 <= N <= 30
1 <= A[i] <= 20
1 <= B <= 100

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Complete search

Starter code: #User function Template for python3

class Solution:
    
    #Function to return a list of indexes denoting the required 
    #combinations whose sum is equal to given number.
    def combinationalSum(self,A, B):
    
        # code here

Solutions:
class Solution:

	def combinationalSum(self, A, B):
		self.ans = []
		A = list(set(A))
		A.sort()

		def recursion(index, ds, B):
			if index == len(A):
				if B == 0:
					self.ans.append(ds)
				return
			if index < len(A) and A[index] <= B:
				recursion(index, ds + [A[index]], B - A[index])
			recursion(index + 1, ds, B)
		recursion(0, [], B)
		return self.ans


class Solution:

	def combinationalSum(self, arr, B):
		arr.sort()
		ds = []
		ans = set()
		n = len(arr)

		def solve(ind, arr, ds, s):
			if s == 0:
				ans.add(tuple(ds))
				return
			if ind >= len(arr) or s < 0:
				return
			if arr[ind] <= s:
				ds.append(arr[ind])
				solve(ind, arr, ds, s - arr[ind])
				ds.pop()
			while ind + 1 < len(arr) and arr[ind + 1] == arr[ind]:
				ind += 1
			solve(ind + 1, arr, ds, s)
		solve(0, arr, ds, B)
		return sorted(list(ans))


class Solution:

	def combinationalSum(self, A, B):
		A = list(sorted(set(A)))
		ans = []

		def solve(i, A, temp, B):
			if i == len(A) or B < 0:
				if B == 0:
					ans.append(temp[:])
				return
			temp.append(A[i])
			solve(i, A, temp, B - A[i])
			temp.pop()
			solve(i + 1, A, temp, B)
		solve(0, A, [], B)
		return sorted(ans)


class Solution:

	def combinationalSum(self, A, B):
		A = list(sorted(set(A)))
		ans = set()

		def solve(i, A, temp, B):
			if i == len(A) or B < 0:
				if B == 0:
					ans.add(tuple(temp))
				return
			temp.append(A[i])
			solve(i, A, temp, B - A[i])
			temp.pop()
			while i + 1 < len(A) and A[i + 1] == A[i]:
				i += 1
			solve(i + 1, A, temp, B)
		solve(0, A, [], B)
		return sorted(list(ans))


class Solution:

	def combinationalSum(self, A, B):

		def combinationSum(A, B, i, sum_arr, result):
			if B == 0:
				sum_arr.sort()
				result.append(sum_arr)
				return
			for j in range(i, len(A)):
				if A[j] > 0:
					if j > i and A[j] == A[j - 1]:
						continue
					if A[j] > B:
						break
					combinationSum(A, B - A[j], j, sum_arr + [A[j]], result)
		result = []
		combinationSum(sorted(A), B, 0, [], result)
		result.sort()
		return result


class Solution:

	def combinationalSum(self, A, B):
		ans = []
		res = []
		A = sorted(list(set(A)))
		n = len(A)

		def bts(i, total):
			if total == B:
				res.append(ans.copy())
				return
			if i >= n:
				return
			if A[i] <= B - total:
				ans.append(A[i])
				bts(i, total + A[i])
				ans.pop()
			bts(i + 1, total)
		bts(0, 0)
		return res


class Solution:

	def helper(self, arr, target, i, ans, temp):
		if i == len(arr):
			if target == 0:
				ans.append(temp[:])
			return
		if arr[i] <= target:
			temp.append(arr[i])
			self.helper(arr, target - arr[i], i, ans, temp)
			temp.pop()
		self.helper(arr, target, i + 1, ans, temp)

	def combinationalSum(self, A, B):
		A = list(sorted(set(A)))
		ans = []
		temp = []
		self.helper(A, B, 0, ans, temp)
		return ans


class Solution:

	def combinationalSum(self, A, B):
		A.sort()
		result = []

		def backtrack(start, current_sum, combination):
			if current_sum == B:
				result.append(combination[:])
				return
			if current_sum > B:
				return
			for i in range(start, len(A)):
				if i > start and A[i] == A[i - 1]:
					continue
				combination.append(A[i])
				backtrack(i, current_sum + A[i], combination)
				combination.pop()
		backtrack(0, 0, [])
		return result


def find(i, arr, cur, x, ds, ans, n):
	if cur > x:
		return ans
	if cur == x:
		ans.append([a for a in ds])
		return ans
	if i < n:
		ds.append(arr[i])
		while i < n - 1:
			if arr[i] == arr[i + 1]:
				i += 1
			else:
				break
		ans = find(i, arr, cur + arr[i], x, ds, ans, n)
		ds.pop()
		ans = find(i + 1, arr, cur, x, ds, ans, n)
	return ans

class Solution:

	def combinationalSum(self, A, B):
		A.sort()
		ans = []
		ds = []
		n = len(A)
		return find(0, A, 0, B, ds, ans, n)


class Solution:

	def combsum(self, A, index, B, seq):
		if B == 0:
			self.res.append(seq)
			return
		if index == len(A):
			return
		quotient = B // A[index]
		for i in range(quotient, -1, -1):
			self.combsum(A, index + 1, B - i * A[index], seq + [A[index]] * i)

	def combinationalSum(self, A, B):
		A = list(set(A))
		A.sort()
		self.res = []
		self.combsum(A, 0, B, [])
		return self.res


class Solution:

	def combinationalSum(self, A, B):
		ans = []
		ds = []

		def solve(index, target, arr, ans, ds):
			if index == len(arr):
				if target == 0:
					ans.append(ds[:])
				return
			if arr[index] <= target:
				ds.append(arr[index])
				solve(index, target - arr[index], arr, ans, ds)
				ds.pop()
			solve(index + 1, target, arr, ans, ds)
		A = list(sorted(set(A)))
		solve(0, B, A, ans, ds)
		return ans


class Solution:

	def helper(self, arr, target, ans, temp):
		if target < 0:
			return
		if target == 0:
			ans.append(temp[:])
			return
		for i in range(len(arr)):
			if arr[i] > target:
				break
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			temp.append(arr[i])
			self.helper(arr[i:], target - arr[i], ans, temp)
			temp.pop()

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


def find_comb(A, B, curr, ans, index, n):
	if B == 0:
		ans.append(curr.copy())
		return
	elif B < 0:
		return
	else:
		for i in range(index, n):
			if B - A[i] >= 0:
				curr.append(A[i])
				find_comb(A, B - A[i], curr, ans, i, n)
				curr.pop(-1)
			else:
				break

class Solution:

	def combinationalSum(self, A, B):
		s = set(A)
		A = list(s)
		A.sort()
		ans = []
		curr = []
		n = len(A)
		find_comb(A, B, curr, ans, 0, n)
		return ans


class Solution:

	def solve(self, arr, tar, ans, tmp):
		if tar < 0:
			return
		if tar == 0:
			ans.append(tmp[:])
			return
		for i in range(len(arr)):
			if arr[i] > tar:
				break
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			tmp.append(arr[i])
			self.solve(arr[i:], tar - arr[i], ans, tmp)
			tmp.pop()

	def combinationalSum(self, A, B):
		A.sort()
		ans = []
		tmp = []
		self.solve(A, B, ans, tmp)
		return ans


class Solution:

	def combinationalSum(self, arr, sum):
		ans = []
		temp = []
		arr = sorted(list(set(arr)))
		self.findNumbers(ans, arr, temp, sum, 0)
		return ans

	def findNumbers(self, ans, arr, temp, sum, index):
		if sum == 0:
			ans.append(list(temp))
			return
		for i in range(index, len(arr)):
			if sum - arr[i] >= 0:
				temp.append(arr[i])
				self.findNumbers(ans, arr, temp, sum - arr[i], i)
				temp.remove(arr[i])


class Solution:

	def combinationalSum(self, A, B):
		setA = set(A)
		A = list(setA)
		A.sort()
		result = []
		self.dfs(0, [], 0, result, A, B)
		return result

	def dfs(self, idx, curr, total, result, source, target):
		if total == target:
			result.append(curr.copy())
			return
		if idx >= len(source) or total > target:
			return
		curr.append(source[idx])
		self.dfs(idx, curr, total + source[idx], result, source, target)
		curr.pop()
		self.dfs(idx + 1, curr, total, result, source, target)


import copy

def helper(k, A, B, ans, temp, res):
	if temp == B:
		a = copy.deepcopy(res)
		ans.append(a)
		return
	for i in range(k, len(A)):
		if temp + A[i] <= B:
			res.append(A[i])
			helper(i, A, B, ans, temp + A[i], res)
			res.pop()
		else:
			break
	return

class Solution:

	def combinationalSum(self, A, B):
		A = list(set(A))
		A.sort()
		ans = []
		temp = 0
		res = []
		b = helper(0, A, B, ans, temp, res)
		ans.sort()
		return ans


class Solution:

	def combinationalSum(self, A, B):

		def backtrack(nums, target, cur):
			if target == 0:
				result.append(cur[:])
				return
			if target < 0:
				return
			for i in range(len(nums)):
				backtrack(nums[i:], target - nums[i], cur + [nums[i]])
		result = []
		A = set(A)
		backtrack(sorted(A), B, [])
		return result


class Solution:

	def combinationalSum(self, A, B):
		ans = []
		ds = []

		def solve(i, arr, tar, ans, ds):
			if i == len(arr):
				if tar == 0:
					ans.append(ds[:])
				return
			if arr[i] <= tar:
				ds.append(arr[i])
				solve(i, arr, tar - arr[i], ans, ds)
				ds.pop()
			solve(i + 1, arr, tar, ans, ds)
		A = list(sorted(set(A)))
		solve(0, A, B, ans, ds)
		return ans


class Solution:

	def combinationalSum(self, arrr, B):
		Aa = set(arrr)
		A = list(Aa)
		A.sort()
		arr = []
		ans = []

		def answ(A, B, ans, arr, j):
			if B == 0:
				arr.append(ans.copy())
				return
			if B < 0:
				return
			for i in range(j, len(A)):
				ans.append(A[i])
				answ(A, B - A[i], ans, arr, i)
				ans.pop()
		answ(A, B, ans, arr, 0)
		return arr


class Solution:

	def gen(self, a, b, leng, pos, brr, arr):
		if pos == leng:
			if b == 0:
				crr = brr.copy()
				arr.add(tuple(crr))
			return
		if 0 > b:
			return
		brr.append(a[pos])
		self.gen(a, b - a[pos], leng, pos, brr, arr)
		brr.pop()
		self.gen(a, b, leng, pos + 1, brr, arr)

	def combinationalSum(self, A, B):
		A = sorted(list(set(A)))
		arr = set()
		brr = []
		self.gen(A, B, len(A), 0, brr, arr)
		arr = list(arr)
		return sorted(arr)


class Solution:

	def combinationalSum(self, A, B):
		self.ans = []
		A = list(set(A))
		A.sort()
		n = len(A)
		arc = []
		idx = 0
		self.solve(A, B, 0, idx, n, arc)
		return self.ans

	def solve(self, A, B, sm, idx, n, arc):
		for i in range(idx, n):
			sm += A[i]
			if sm == B:
				arc.append(A[i])
				self.ans.append(arc.copy())
				arc.pop()
				break
			elif sm < B:
				arc.append(A[i])
				self.solve(A, B, sm, i, n, arc)
				arc.pop()
			else:
				break
			sm -= A[i]


class Solution:

	def combinationalSum(self, candidates, target):
		res = []
		candidates = list(set(candidates))
		candidates.sort()
		su = 0

		def comb(ind, arr, su):
			if ind >= len(candidates):
				return
			if su == target:
				res.append(arr.copy())
				return
			if su > target:
				return
			for i in range(ind, len(candidates)):
				if i > ind and candidates[i - 1] == candidates[i]:
					continue
				if candidates[i] > target:
					break
				arr.append(candidates[i])
				su += candidates[i]
				comb(i, arr, su)
				su -= candidates[i]
				arr.pop()
		comb(0, [], su)
		return res


class Solution:

	def is_valid_state(self, state, num, B):
		if len(state):
			return num <= B and num >= state[-1] and (sum(state) + num <= B)
		else:
			return True

	def traverse(self, A, B, state):
		current_sum = sum(state)
		if current_sum == B:
			self.results.append(state.copy())
			return
		else:
			for num in A:
				if self.is_valid_state(state, num, B):
					state.append(num)
					self.traverse(A, B, state)
					state.pop()

	def combinationalSum(self, A, B):
		self.results = []
		state = []
		self.traverse(set(A), B, state)
		return sorted(self.results)


class Solution:

	def combinationalSum(self, arr, B):
		arr = sorted(list(set(arr)))
		res = []
		n = len(arr)

		def backtrack(curr_sum, start, path):
			if curr_sum == B:
				res.append(path[:])
				return
			for i in range(start, n):
				num = arr[i]
				if curr_sum + num > B:
					break
				path.append(num)
				backtrack(curr_sum + num, i, path)
				path.pop()
		backtrack(0, 0, [])
		return res


class Solution:

	def combinationalSum(self, a, b):
		s = []
		temp = []
		i = 0
		a = sorted(list(set(a)))

		def comination(i, b, s):
			if i == len(a):
				if b == 0:
					temp.append(list(s))
				return
			if a[i] <= b:
				s.append(a[i])
				comination(i, b - a[i], s)
				s.remove(a[i])
			comination(i + 1, b, s)
		comination(i, b, s)
		return temp


class Solution:

	def combinationalSum(self, A, B):
		A = sorted(list(set(A)))
		n = len(A)
		ans = []
		l = []
		self.combi_sum(A, n, 0, l, B, ans)
		return ans

	def combi_sum(self, arr, n, idx, l, sum, ans):
		if sum == 0:
			ans.append(list(l))
			return
		for i in range(idx, n):
			if sum - arr[i] >= 0:
				l.append(arr[i])
				self.combi_sum(arr, n, i, l, sum - arr[i], ans)
				l.remove(arr[i])


class Solution:

	def combinationalSum(self, arr, target):
		arr = list(sorted(set(arr)))
		li = []
		temparr = []

		def solve(i, target, arr, li, temparr):
			if i == len(arr):
				if target == 0:
					li.append(temparr[:])
				return
			if arr[i] <= target:
				temparr.append(arr[i])
				solve(i, target - arr[i], arr, li, temparr)
				temparr.pop()
			solve(i + 1, target, arr, li, temparr)
		solve(0, target, arr, li, temparr)
		return li


class Solution:

	def helper(self, arr, target, idx, l, res):
		if target == 0:
			res.append(l[:])
			return
		for i in range(idx, len(arr)):
			if i > idx and arr[i] == arr[i - 1]:
				continue
			if arr[i] > target:
				break
			l.append(arr[i])
			self.helper(arr, target - arr[i], i, l, res)
			l.pop()

	def combinationalSum(self, A, B):
		l = []
		res = []
		A.sort()
		self.helper(A, B, 0, l, res)
		return res


class Solution:

	def combinationalSum(self, arr, target):
		arr = list(set(arr))
		arr.sort()
		ans = []

		def dfs(pos, res, total):
			if pos >= len(arr) or total > target:
				return
			if total == target:
				ans.append(res.copy())
			for i in range(pos, len(arr)):
				res.append(arr[i])
				dfs(i, res, total + arr[i])
				res.pop()
		dfs(0, [], 0)
		return ans


class Solution:

	def combinationalSum(self, arr, target):
		arr.sort()
		ans = []

		def dfs(pos, res, total):
			if pos >= len(arr) or total > target:
				return
			if total == target:
				ans.append(res.copy())
			for i in range(pos, len(arr)):
				if i > 0 and arr[i] == arr[i - 1]:
					continue
				res.append(arr[i])
				dfs(i, res, total + arr[i])
				res.pop()
		dfs(0, [], 0)
		return ans


import copy

class Solution:

	def combinationalSum(self, A, B):
		final_list = []
		currenlist = []
		arr = sorted(list(set(A)))

		def helper(arr, sum, index):
			if sum == 0:
				final_list.append(copy.copy(currenlist))
				return final_list
			for i in range(index, len(arr)):
				if sum - arr[i] >= 0:
					currenlist.append(arr[i])
					helper(arr, sum - arr[i], i)
					currenlist.remove(arr[i])
		helper(arr, B, 0)
		return final_list


def solve(sm, arr, n, comb):
	global ans
	if sm == 0:
		ans.append(comb)
		return
	elif n == 0:
		return
	if sm >= arr[n - 1]:
		solve(sm - arr[n - 1], arr, n, comb + [arr[n - 1]])
		solve(sm, arr, n - 1, comb)
		return
	else:
		return

class Solution:

	def combinationalSum(self, A, B):
		global ans
		ans = []
		A.sort(reverse=True)
		uni = [A[0]]
		for i in range(1, len(A)):
			if uni[-1] != A[i]:
				uni.append(A[i])
		solve(B, uni, len(uni), [])
		return ans


class Solution:

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

		def funcall(index, temp, sumtillnow):
			if sumtillnow == B:
				ans.append(temp.copy())
				return
			if sumtillnow > B or index == len(A):
				return
			temp.append(A[index])
			funcall(index, temp, sumtillnow + A[index])
			temp.pop()
			funcall(index + 1, temp, sumtillnow)
		A = list(set(A))
		A.sort()
		funcall(0, temp, 0)
		return ans


class Solution:

	def combinationalSum(self, A, B):
		arr = A
		sum = B

		def combinationSum(arr, sum):
			ans = []
			temp = []
			arr = sorted(arr)
			findNumbers(ans, arr, temp, sum, 0)
			return list(ans)

		def findNumbers(ans, arr, temp, sum, index):
			if sum == 0:
				ans.append(list(temp))
				return
			for i in range(index, len(arr)):
				if i > index and arr[i] == arr[i - 1]:
					continue
				if sum - arr[i] >= 0:
					temp.append(arr[i])
					findNumbers(ans, arr, temp, sum - arr[i], i)
					temp.pop()
		return combinationSum(arr, sum)


class Solution:

	def combinationalSum(self, candidates, target):
		ans = []
		ds = []
		candidates = list(sorted(set(candidates)))

		def findcombination(ind, target):
			if ind == len(candidates):
				if target == 0:
					ans.append(ds[:])
				return
			if candidates[ind] <= target:
				ds.append(candidates[ind])
				findcombination(ind, target - candidates[ind])
				ds.pop()
			findcombination(ind + 1, target)
		findcombination(0, target)
		return ans


class Solution:

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

	def combinationalSum(self, A, B):
		A.sort()
		self.solve(A, B, [])
		return self.ans

	def solve(self, arr, s, temp):
		if s == 0:
			self.ans.append(temp.copy())
			return
		for i in range(len(arr)):
			if arr[i] > s:
				break
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			if arr[i] <= s:
				temp.append(arr[i])
				s = s - arr[i]
				self.solve(arr[i:], s, temp)
				s += temp.pop()


class Solution:

	def combinationalSum(self, A, B):
		A = list(sorted(set(A)))
		ans = []

		def help(ans, A, arr, val, index):
			if val == 0:
				ans.append(list(arr))
				return
			for i in range(index, len(A)):
				if val - A[i] >= 0:
					arr.append(A[i])
					help(ans, A, arr, val - A[i], i)
					arr.remove(A[i])
		help(ans, A, [], B, 0)
		return ans


class Solution:

	def solve(self, arr, target, ans, tmp, index):
		if target == 0:
			ans.append(tmp[:])
			return
		for i in range(index, len(arr)):
			if target >= arr[i]:
				tmp.append(arr[i])
				self.solve(arr, target - arr[i], ans, tmp, i)
				tmp.pop()

	def combinationalSum(self, A, B):
		arr = sorted(set(A))
		(ans, tmp) = ([], [])
		self.solve(arr, B, ans, tmp, 0)
		return ans


class Solution:

	def combinationalSum(self, A, B):
		combinations = []
		A.sort(reverse=True)
		a = []
		for x in A:
			if not a or a[-1] != x:
				a.append(x)
		self.combinationHelper(a, len(a), B, [], combinations)
		return combinations

	def combinationHelper(self, A, n, sum, comb, combinations):
		if sum == 0:
			combinations.append(list(comb))
			return
		if n == 0 or sum < 0:
			return
		if A[n - 1] <= sum:
			comb.append(A[n - 1])
			self.combinationHelper(A, n, sum - A[n - 1], comb, combinations)
			comb.remove(A[n - 1])
		self.combinationHelper(A, n - 1, sum, comb, combinations)


class Solution:

	def helper(self, A, B, arr, idx, temp):
		if B == 0:
			arr.append(temp.copy())
			return
		for i in range(idx, len(A)):
			if i > idx and A[i] == A[i - 1]:
				continue
			if B >= A[i]:
				temp.append(A[i])
				self.helper(A, B - A[i], arr, i, temp)
				temp.pop()

	def combinationalSum(self, A, B):
		arr = []
		A = sorted(A)
		self.helper(A, B, arr, 0, [])
		return sorted(arr)


class Solution:

	def f(self, ind, A, target, l, ans):
		if ind == len(A):
			if target == 0:
				k = list(l)
				ans.append(k)
			return
		l.append(A[ind])
		if A[ind] <= target:
			self.f(ind, A, target - A[ind], l, ans)
		l.pop()
		self.f(ind + 1, A, target, l, ans)

	def combinationalSum(self, A, B):
		l = []
		ans = []
		A = sorted(list(set(A)))
		self.f(0, A, B, l, ans)
		ans.sort()
		return ans


class Solution:

	def combinationalSum(self, A, B):
		A = list(sorted(set(A)))
		N = len(A)

		def com(i, A, B, curr, l, res):
			if i == len(A):
				if B == 0:
					res.append(l[:])
				return
			if A[i] <= B:
				l.append(A[i])
				com(i, A, B - A[i], curr, l, res)
				l.pop()
			com(i + 1, A, B, curr, l, res)
		res = []
		com(0, A, B, 0, [], res)
		return res


class Solution:

	def combinationalSum(self, A, B):
		a = set(A)
		arr = list(a)
		arr.sort()
		ans = []
		self.dfs(arr, B, [], ans)
		return ans

	def dfs(self, arr, B, path, ans):
		if B < 0:
			return
		if B == 0:
			ans.append(path)
			return
		for i in range(len(arr)):
			self.dfs(arr[i:], B - arr[i], path + [arr[i]], ans)


class Solution:

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

	def combinationalSum(self, arr, s):
		arr = list(set(arr))
		arr.sort()
		self.rec(arr, s, [], 0, len(arr))
		return self.ans

	def rec(self, arr, s, temp, i, l):
		if s == 0:
			self.ans.append(list(temp))
			return
		for i in range(i, l):
			if s - arr[i] >= 0:
				temp.append(arr[i])
				self.rec(arr, s - arr[i], temp, i, l)
				temp.pop()
		return


class Solution:

	def combinationalSum(self, A, B):

		def remove_duplicate(arr):
			new_arr = []
			for i in range(len(arr)):
				if arr[i] in new_arr:
					continue
				else:
					new_arr.append(arr[i])
			return new_arr

		def helper(index, A, B, ds, ans):
			if index == len(A):
				if B == 0:
					ans.append(ds[:])
				return
			if A[index] <= B:
				ds.append(A[index])
				helper(index, A, B - A[index], ds, ans)
				ds.pop()
			helper(index + 1, A, B, ds, ans)
		y = remove_duplicate(A)
		y.sort()
		ans = []
		helper(0, y, B, [], ans)
		return ans


class Solution:

	def solve(self, arr, su, lis, res):
		if su < 0:
			return
		if su == 0:
			res.append(lis[:])
			return
		for i in range(len(arr)):
			if arr[i] > su:
				break
			lis.append(arr[i])
			self.solve(arr[i:], su - arr[i], lis, res)
			lis.pop()

	def combinationalSum(self, A, B):
		arr = list(set(A))
		arr.sort()
		res = []
		self.solve(arr, B, [], res)
		return res


class Solution:

	def solve(self, arr, tar, ans, tmp):
		if tar < 0:
			return
		if tar == 0:
			ans.append(tmp[:])
			return
		for i in range(len(arr)):
			if arr[i] > tar:
				break
			tmp.append(arr[i])
			self.solve(arr[i:], tar - arr[i], ans, tmp)
			tmp.pop()

	def combinationalSum(self, A, B):
		A = list(set(A))
		A.sort()
		ans = []
		tmp = []
		self.solve(A, B, ans, tmp)
		return ans


class Solution:

	def combinationalSum(self, arr, B):
		ans = []
		dummy = []
		i = 0
		arr = sorted(list(set(arr)))
		self.answer(arr, B, i, dummy, ans)
		return ans

	def answer(self, arr, B, i, dummy, ans):
		if B == 0:
			ans.append(list(dummy))
			return
		for x in range(i, len(arr)):
			if B - arr[x] >= 0:
				dummy.append(arr[x])
				self.answer(arr, B - arr[x], x, dummy, ans)
				dummy.remove(arr[x])


class Solution:

	def recurse(self, ans, current, index, target, A):
		if target == 0:
			ans.append(list(current))
		elif target < 0 or index >= len(A):
			return
		else:
			current.append(A[index])
			self.recurse(ans, current, index, target - A[index], A)
			index += 1
			current.pop()
			self.recurse(ans, current, index, target, A)

	def combinationalSum(self, A, B):
		ans = []
		current = []
		A = list(set(A))
		self.recurse(ans, current, 0, B, sorted(A))
		return ans


class Solution:

	def combinationalSum(self, candidates, target):
		i = 0
		curr = []
		s = 0
		res = []

		def solve(i, curr, s):
			if s == target:
				res.append(curr.copy())
				return
			if s > target or i >= len(candidates):
				return
			curr.append(candidates[i])
			solve(i, curr, s + candidates[i])
			curr.pop()
			solve(i + 1, curr, s)
		candidates = list(set(candidates))
		solve(0, curr, s)
		for i in res:
			i.sort()
		res.sort()
		return res


class Solution:

	def combi(self, arr, index, target, lst, combinations):
		if index == len(arr):
			if target == 0:
				combinations.append(lst[:])
			return
		if arr[index] <= target:
			lst.append(arr[index])
			self.combi(arr, index, target - arr[index], lst, combinations)
			lst.remove(arr[index])
		self.combi(arr, index + 1, target, lst, combinations)

	def combinationalSum(self, A, B):
		A = list(set(A))
		A.sort()
		lst = []
		combinations = []
		self.combi(A, 0, B, lst, combinations)
		return combinations


class Solution:

	def combinationalSum(self, A, B):
		k = sorted(list(set(A)))
		l = []

		def f(i, sm, t=[]):
			if sm == 0:
				l.append(list(t))
				return
			for j in range(i, len(k)):
				if sm - k[j] >= 0:
					t.append(k[j])
					f(j, sm - k[j], t)
					t.pop()
				else:
					return
		f(0, B)
		return l


class Solution:

	def combsumutil(self, A, B, N, res, temp, index):
		if index >= N or B < 0:
			return
		if B == 0:
			res.append(list(temp))
			return
		temp.append(A[index])
		self.combsumutil(A, B - temp[-1], N, res, temp, index)
		temp.pop()
		self.combsumutil(A, B, N, res, temp, index + 1)

	def combinationalSum(self, A, B):
		A = set(A)
		A = list(A)
		A.sort()
		res = []
		self.combsumutil(A, B, len(A), res, [], 0)
		return res


class Solution:

	def helper(self, ind, target, ds, ans, candidates, N):
		if ind == N:
			if target == 0:
				ans.append(ds[:])
			return
		if candidates[ind] <= target:
			ds.append(candidates[ind])
			self.helper(ind, target - candidates[ind], ds, ans, candidates, N)
			ds.pop()
		self.helper(ind + 1, target, ds, ans, candidates, N)

	def combinationalSum(self, A, B):
		A = list(set(A))
		A.sort()
		ans = []
		ds = []
		self.helper(0, B, ds, ans, A, len(A))
		return ans


class Solution:

	def combinationalSum(self, A, B):
		A.sort()

		def go(i, k, s):
			if k > B:
				return
			if k == B:
				ans.append(s)
				return
			if i == len(A):
				return
			if i != len(A) - 1 and A[i] == A[i + 1]:
				go(i + 1, k, s)
				return
			go(i, k + A[i], s + [A[i]])
			go(i + 1, k, s)
		ans = []
		go(0, 0, [])
		return ans


class Solution:

	def combinationalSum(self, arr, tar):
		arr = sorted(list(set(arr)))
		res = []
		inc = set()
		combi = []

		def fincom(i, s, k):
			if s == k:
				temp = [x for x in combi]
				res.append(temp)
				return
			if i >= len(arr) or s > k:
				return
			combi.append(arr[i])
			fincom(i, s + arr[i], k)
			combi.pop(-1)
			fincom(i + 1, s, k)
			return
		fincom(0, 0, tar)
		return list(res)


class Solution:

	def combinationalSum(self, A, B):
		arr = []

		def helper(i, A, B, temp, arr):
			if i == N:
				if B == 0:
					arr.append(temp[:])
				return
			if A[i] <= B:
				temp.append(A[i])
				helper(i, A, B - A[i], temp, arr)
				temp.pop()
			helper(i + 1, A, B, temp, arr)
		A = list(set(A))
		A.sort()
		N = len(A)
		helper(0, A, B, [], arr)
		return arr


class Solution:

	def combinationalSum(self, A, B):
		ans = []

		def findCombination(ind, target, arr, ans, ds):
			if ind == len(arr):
				if target == 0:
					ans.append(ds[:])
				return
			if arr[ind] <= target:
				ds.append(arr[ind])
				findCombination(ind, target - arr[ind], arr, ans, ds)
				ds.pop()
			findCombination(ind + 1, target, arr, ans, ds)
		A = list(sorted(set(A)))
		findCombination(0, B, A, ans, [])
		return ans


class Solution:

	def combinationalSum(self, A, B):
		A = set(A)
		A = list(A)
		A.sort()
		if A[0] > B:
			return []
		res = []
		self.func(A, len(A), B, res, [], 0)
		return res

	def func(self, A, n, B, res, combination, index):
		if B == 0:
			res.append(list(combination))
			return
		while index < n and B >= A[index]:
			combination.append(A[index])
			self.func(A, n, B - A[index], res, combination, index)
			index += 1
			combination.pop()
		return


class Solution:

	def f(self, candidates, ind, target, ans, ds):
		if ind == len(candidates):
			if target == 0:
				ans.append(ds)
			return
		if target >= candidates[ind]:
			self.f(candidates, ind, target - candidates[ind], ans, ds + [candidates[ind]])
		self.f(candidates, ind + 1, target, ans, ds)

	def combinationalSum(self, A, B):
		unique = set(A)
		new_arr = list(unique)
		new_arr.sort()
		ans = []
		ds = []
		n = len(A)
		self.f(new_arr, 0, B, ans, ds)
		return ans


class Solution:

	def solve(self, ind, tar, nums, ans, tmp):
		if ind == len(nums):
			if tar == 0:
				ans.append(tmp[:])
			return
		if tar >= nums[ind]:
			tmp.append(nums[ind])
			self.solve(ind, tar - nums[ind], nums, ans, tmp)
			tmp.pop()
		self.solve(ind + 1, tar, nums, ans, tmp)

	def combinationalSum(self, A, B):
		A = list(set(A))
		A.sort()
		ans = []
		tmp = []
		self.solve(0, B, A, ans, tmp)
		return ans


class Solution:

	def combinationalSum(self, arr, target):
		ds = []
		a = []
		arr.sort()
		ind = 0

		def comb(ind, arr, t, a, ds):
			if t == 0:
				a.append(ds.copy())
				return
			if t < 0:
				return
			for i in range(ind, len(arr)):
				if i > ind and arr[i] == arr[i - 1]:
					continue
				if arr[i] > target:
					break
				ds.append(arr[i])
				comb(i, arr, t - arr[i], a, ds)
				ds.remove(arr[i])
		comb(ind, arr, target, a, ds)
		return a