You are given a collection of numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to the target. Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Example: 
Input:  candidates = [10,1,2,7,6,1,5], target = 8. 
Output:  [[1,1,6], [1,2,5], [1,7], [2,6]]. 
Explanation:  These are the unique combinations whose sum is equal to the target.
Your Task:
Complete the function vector> combinationSum2(), which takes a vector "candidates" and an integer target and returns a vector of vector consisting of all unique combinations whose sum is equal to the target.
Expected Time Complexity: O(2^{n*k}).
Expected Auxiliary Space: O(k*x).
Constraints:
1 <= candidates.length <= 100.
1 <= candidates[i] <= 50.
1 <= target <= 30.

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def combinationSum2(self, candidates, target):

        # Code here

Solutions:
def combisum2(i, target, subs, arr, ans, n):
	if i == n:
		if target == 0:
			ans.append(subs[:])
		return
	if target - arr[i] >= 0:
		subs.append(arr[i])
		combisum2(i + 1, target - arr[i], subs, arr, ans, n)
		subs.pop()
	while i < n - 1 and arr[i] == arr[i + 1]:
		i += 1
	combisum2(i + 1, target, subs, arr, ans, n)

class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ans = []
		subs = []
		i = 0
		n = len(candidates)
		combisum2(i, target, subs, candidates, ans, n)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		ans = []
		candidates.sort()

		def combi(ind, lst, target):
			if target == 0:
				ans.append(lst)
				return
			for i in range(ind, len(candidates)):
				if i > ind and candidates[i] == candidates[i - 1]:
					continue
				if candidates[i] > target:
					break
				combi(i + 1, lst + [candidates[i]], target - candidates[i])
		combi(0, [], target)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		ans = set()
		A = list(sorted(candidates))

		def solve(i, temp, tgt):
			if tgt == 0:
				ans.add(tuple(sorted(temp)))
				return
			if i >= len(A):
				return
			for j in range(i, len(A)):
				if j > i and A[j] == A[j - 1]:
					continue
				if A[j] > tgt:
					break
				temp.append(A[j])
				solve(j + 1, temp, tgt - A[j])
				temp.pop()
		solve(0, [], target)
		return list(ans)
		solve(0, [], target)
		return sorted(list(ans))


class Solution:

	def solve(self, c, k, t, curr):
		if t == 0:
			self.ans.append(curr.copy())
			return
		if t < 0 or k == n:
			return
		if t < c[k]:
			return
		curr.append(c[k])
		self.solve(c, k + 1, t - c[k], curr)
		curr.pop()
		j = k + 1
		while j < n and c[j] == c[k]:
			j += 1
		self.solve(c, j, t, curr)

	def combinationSum2(self, candidates, target):
		candidates.sort()
		self.ans = []
		self.solve(candidates, 0, target, [])
		return self.ans


class Solution:

	def combsum(self, A, index, B, seq):
		if B == 0:
			self.res.append(seq)
			return
		if index == len(A):
			return
		if B >= A[index]:
			self.combsum(A, index + 1, B - A[index], seq + [A[index]])
			while index < len(A) - 1 and A[index] == A[index + 1]:
				index += 1
			self.combsum(A, index + 1, B, seq)

	def combinationSum2(self, candidates, target):
		candidates.sort()
		self.res = []
		self.combsum(candidates, 0, target, [])
		return self.res


class Solution:

	def combsum(self, A, index, B, seq):
		if B == 0:
			if seq not in self.res:
				self.res.append(seq)
			return
		if index == len(A):
			return
		if B >= A[index]:
			if not (index != 0 and (A[index - 1] == A[index] and (len(seq) == 0 or seq[-1] != A[index]))):
				self.combsum(A, index + 1, B - A[index], seq + [A[index]])
			self.combsum(A, index + 1, B, seq)

	def combinationSum2(self, candidates, target):
		candidates.sort()
		self.res = []
		self.combsum(candidates, 0, target, [])
		return self.res


class Solution:

	def _combinationSum2(self, ind, array, target, ans, ds):
		if target == 0:
			ans.append(ds[:])
			return
		for i in range(ind, len(array)):
			if array[i] > target:
				break
			if i > ind and array[i] == array[i - 1]:
				continue
			ds.append(array[i])
			self._combinationSum2(i + 1, array, target - array[i], ans, ds)
			ds.pop()

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ans = []
		ds = []
		self._combinationSum2(0, candidates, target, ans, ds)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()
		(arr, combinations, lengthOfCandidates) = ([], [], len(candidates))
		self.noOfCombinations(0, target, arr, combinations, candidates, lengthOfCandidates)
		return combinations

	def noOfCombinations(self, n, target, arr, combinations, candidates, lengthOfCandidates):
		if target == 0:
			temp = [ele for ele in arr]
			combinations.append(temp)
			return
		if n == lengthOfCandidates:
			return
		prev = None
		for i in range(n, lengthOfCandidates):
			if candidates[i] <= target and candidates[i] != prev:
				prev = candidates[i]
				arr.append(candidates[i])
				self.noOfCombinations(i + 1, target - candidates[i], arr, combinations, candidates, lengthOfCandidates)
				arr.pop()


class Solution:

	def combinationSum2(self, candidates, target):

		def combination2(ind, arr, target):
			if target == 0:
				ans.append(s[:])
				return
			for i in range(ind, len(arr)):
				if i > ind and arr[i] == arr[i - 1]:
					continue
				if arr[i] > target:
					break
				s.append(arr[i])
				combination2(i + 1, arr, target - arr[i])
				s.pop()
		ans = []
		s = []
		candidates.sort()
		combination2(0, candidates, target)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		result = []
		temp = []
		candidates.sort()

		def combination(ind, target):
			if target == 0:
				result.append(temp[:])
				return
			for i in range(ind, len(candidates)):
				if i > ind and candidates[i] == candidates[i - 1]:
					continue
				if candidates[i] > target:
					break
				temp.append(candidates[i])
				combination(i + 1, target - candidates[i])
				temp.pop()
		combination(0, target)
		return list(result)


class Solution:

	def subsetsum(self, ind, n, lst, num, k, ans):
		if k == 0:
			ans.add(tuple(lst))
			return
		for i in range(ind, n):
			if i > ind:
				if num[i] == num[i - 1]:
					continue
			if k < num[i]:
				break
			lst.append(num[i])
			self.subsetsum(i + 1, n, lst, num, k - num[i], ans)
			lst.pop()

	def combinationSum2(self, num, k):
		num.sort()
		ans = set()
		lst = []
		n = len(num)
		self.subsetsum(0, n, lst, num, k, ans)
		return list(ans)


class Solution:

	def combinationSum2(self, candidates, target):
		ans = []
		d = []
		candidates.sort()

		def r(ie, target):
			if target == 0:
				ans.append(d[:])
				return
			for i in range(ie, len(candidates)):
				if i > ie and candidates[i] == candidates[i - 1]:
					continue
				if candidates[ie] > target:
					break
				d.append(candidates[i])
				r(i + 1, target - candidates[i])
				d.pop()
		r(0, target)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		ans = []
		candidates.sort()

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


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ans = []
		temp = []

		def funcall(index, sumtillnow, temp):
			if sumtillnow == target:
				ans.append(temp.copy())
				return
			if sumtillnow > target or index == len(candidates):
				return
			for i in range(index, len(candidates)):
				if i == index or candidates[i] != candidates[i - 1]:
					temp.append(candidates[i])
					funcall(i + 1, sumtillnow + candidates[i], temp)
					temp.pop()
		funcall(0, 0, temp)
		return ans


class Solution:

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

		def combi(ind, target):
			if target == 0:
				ans.append(ds[:])
				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])
				combi(i + 1, target - arr[i])
				ds.pop()
		combi(0, target)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		ind = 0
		res = []
		ans = []
		candidates.sort()

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


class Solution:

	def f(self, ind, target, candidates, l, ans):
		if target == 0:
			ans.append(list(l))
			return
		for i in range(ind, len(candidates)):
			if i > ind and candidates[i] == candidates[i - 1]:
				continue
			if candidates[i] > target:
				break
			l.append(candidates[i])
			self.f(i + 1, target - candidates[i], candidates, l, ans)
			l.pop()

	def combinationSum2(self, candidates, target):
		candidates.sort()
		l = []
		ans = []
		self.f(0, target, candidates, l, ans)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()

		def com(ind, N, candidates, target, l, res):
			if target == 0:
				res.append(l[:])
				return
			for i in range(ind, N):
				if i > ind and candidates[i] == candidates[i - 1]:
					continue
				if candidates[i] > target:
					return
				l.append(candidates[i])
				com(i + 1, N, candidates, target - candidates[i], l, res)
				l.pop()
		res = []
		N = len(candidates)
		com(0, N, candidates, target, [], res)
		return res


class Solution:

	def solve(self, arr, index, target, some, lst, ans):
		if some <= 0 or index >= len(arr) or some - arr[index] < 0:
			return
		if some - arr[index] == 0:
			ans.add(tuple(lst + [arr[index]]))
			return
		if some - arr[index] > 0:
			self.solve(arr, index + 1, target, some - arr[index], lst + [arr[index]], ans)
			self.solve(arr, index + 1, target, some, lst, ans)

	def combinationSum2(self, arr, target):
		arr.sort()
		ans = set()
		self.solve(arr, 0, target, target, [], ans)
		return list(ans)


class Solution:

	def combinationSum2(self, candidates, target):
		arr = sorted(candidates)
		n = len(arr)

		def solve(idx, arr, target, l, ans):
			if target == 0:
				ans.append(l.copy())
				return
			for i in range(idx, n):
				if i > idx and arr[i] == arr[i - 1]:
					continue
				if arr[i] > target:
					break
				l.append(arr[i])
				solve(i + 1, arr, target - arr[i], l, ans)
				l.pop()
		ans = []
		solve(0, arr, target, [], ans)
		return ans


class Solution:

	def combinationSum2(self, arr, target):
		arr.sort()
		res = []

		def helper(idx, target, temp):
			if target == 0:
				res.append(temp.copy())
			if target <= 0:
				return
			prev = -1
			for i in range(idx, len(arr)):
				if arr[i] == prev:
					continue
				temp.append(arr[i])
				helper(i + 1, target - arr[i], temp)
				temp.pop()
				prev = arr[i]
		helper(0, target, [])
		return res


class Solution:

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

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ds = []
		ans = []
		self.helper(0, target, ds, ans, candidates, len(candidates))
		return ans


class Solution:

	def combinationSum2(self, candidates, target):

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


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()
		res = []
		cur = []

		def backtrack(pos, total):
			if total == 0:
				res.append(cur.copy())
			if total <= 0:
				return
			prev = -1
			for i in range(pos, len(candidates)):
				if candidates[i] == prev:
					continue
				cur.append(candidates[i])
				backtrack(i + 1, total - candidates[i])
				cur.pop()
				prev = candidates[i]
		backtrack(0, target)
		return res


class Solution:

	def combinationSum2(self, candidates, target):
		ds = []
		a = []
		candidates.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 + 1, arr, t - arr[i], a, ds)
				ds.remove(arr[i])
		comb(ind, candidates, target, a, ds)
		return a


class Solution:

	def combinationSum2(self, arr, target):

		def backtrack(i, arr, curr, res, n, target, currsumm):
			if currsumm > target:
				return
			if currsumm == target:
				res.append(curr.copy())
				return
			for ind in range(i, n):
				if arr[ind] == arr[ind - 1] and ind > i:
					continue
				currsumm += arr[ind]
				curr.append(arr[ind])
				backtrack(ind + 1, arr, curr, res, n, target, currsumm)
				currsumm -= arr[ind]
				curr.pop()
				if arr[ind] > target:
					break
			return res
		arr.sort()
		return backtrack(0, arr, [], [], len(arr), target, 0)


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()
		res = []

		def get_sum(inp, cursum, tgt, ans):
			for i in range(len(inp)):
				ele = inp[i]
				if i > 0 and inp[i] == inp[i - 1]:
					continue
				if cursum + ele == tgt:
					if ans + [ele] not in res:
						res.append(ans + [ele])
				elif cursum + ele < tgt:
					if i < len(inp) - 1:
						get_sum(inp[i + 1:], cursum + ele, tgt, ans + [ele])
				else:
					break
		get_sum(candidates, 0, target, [])
		return res


class Solution:

	def combination2(self, arr, n, ind, ds, target, res):
		if target == 0:
			ds = ds.copy()
			res.append(ds)
		for i in range(ind, n):
			if i > ind and arr[i] == arr[i - 1]:
				continue
			if arr[i] > target:
				break
			ds.append(arr[i])
			self.combination2(arr, n, i + 1, ds, target - arr[i], res)
			ds.remove(arr[i])

	def combinationSum2(self, candidates, target):
		candidates.sort()
		res = []
		ds = []
		n = len(candidates)
		self.combination2(candidates, n, 0, ds, target, res)
		return res


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()

		def funk(a, s, t, ans, fans, d):
			if s == len(a):
				if t == 0:
					fans += [ans]
				return
			for i in range(s, len(a)):
				if a[i] not in d and a[i] <= t:
					funk(a, i + 1, t - a[i], ans + [a[i]], fans, {})
					d[a[i]] = 0
			funk(a, i + 1, t, ans, fans, d)
			return
		fans = []
		ans = []
		funk(candidates, 0, target, ans, fans, {})
		return fans


class Solution:

	def combinationSum2(self, candidates, target):
		res = []
		candidates.sort()

		def combination(pos, temp, candidates, target, res):
			if target == 0:
				res.append(temp.copy())
				return
			if target <= 0:
				return
			prev = -1
			for i in range(pos, len(candidates)):
				if candidates[i] == prev:
					continue
				temp.append(candidates[i])
				combination(i + 1, temp, candidates, target - candidates[i], res)
				temp.pop()
				prev = candidates[i]
		combination(0, [], candidates, target, res)
		return res


class Solution:

	def combinationSum2(self, candidates, target):
		arr = []

		def backtrack(c, t, ind, ds):
			if t == 0:
				arr.append(ds[:])
				return
			for i in range(ind, len(c)):
				if c[i] > t:
					break
				if i > ind and c[i] == c[i - 1]:
					continue
				ds.append(c[i])
				backtrack(c, t - c[i], i + 1, ds)
				ds.pop()
		candidates.sort()
		backtrack(candidates, target, 0, [])
		return arr


class Solution:

	def combinationSum2(self, arr, target):
		arr.sort()
		res = []

		def helper(ind, tar, tmp):
			if tar == 0:
				res.append(tmp[:])
				return
			for i in range(ind, len(arr)):
				if i > ind and arr[i] == arr[i - 1]:
					continue
				if tar < arr[i]:
					continue
				tmp.append(arr[i])
				helper(i + 1, tar - arr[i], tmp)
				tmp.pop()
		helper(0, target, [])
		return res


class Solution:

	def combinationSum2(self, candidates, target):

		def rec(idx, target, arr, ans, ds):
			if target == 0:
				ans.append(ds.copy())
				return
			for i in range(idx, len(arr)):
				if i > idx and arr[i] == arr[i - 1]:
					continue
				if arr[i] > target:
					break
				ds.append(arr[i])
				rec(i + 1, target - arr[i], arr, ans, ds)
				ds.pop()
		candidates.sort()
		ans = []
		ds = []
		rec(0, target, candidates, ans, ds)
		return ans


class Solution:

	def findCombinations(self, index, arr, target, ans, ds):
		if target == 0:
			ans.append([ele for ele in ds])
			return
		for i in range(index, len(arr)):
			if i > index and arr[i] == arr[i - 1]:
				continue
			if arr[i] > target:
				break
			ds.append(arr[i])
			self.findCombinations(i + 1, arr, target - arr[i], ans, ds)
			ds.pop()

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ans = []
		ds = []
		self.findCombinations(0, candidates, target, ans, ds)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		arr = candidates
		arr.sort()
		ans = []
		sum = target
		temp = []

		def combination(arr, sum, ans, temp, index):
			if sum == 0:
				ans.append(temp.copy())
				return
			for i in range(index, len(arr)):
				if i > index and arr[i] == arr[i - 1]:
					continue
				if arr[i] > target:
					break
				if sum - arr[index] >= 0:
					temp.append(arr[i])
					combination(arr, sum - arr[i], ans, temp, i + 1)
					temp.remove(arr[i])
		combination(arr, sum, ans, temp, 0)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ls = []
		res = []

		def recur(ind, ar, target, ls):
			if target == 0:
				res.append(ls.copy())
				return
			if target < 0:
				return
			prev = -1
			for i in range(ind, len(candidates)):
				if ar[i] == prev:
					continue
				if ar[i] > target:
					break
				ls.append(ar[i])
				recur(i + 1, ar, target - ar[i], ls)
				prev = ar[i]
				ls.pop()
		recur(0, candidates, target, ls)
		return res


class Solution:

	def f(self, ind, target, arr, ds, ans):
		if target == 0:
			ans.append(list(ds))
			return
		i = ind
		while i < len(arr):
			if i > ind and arr[i] == arr[i - 1]:
				i += 1
				continue
			if arr[i] > target:
				i += 1
				break
			ds.append(arr[i])
			self.f(i + 1, target - arr[i], arr, ds, ans)
			ds.pop()
			i += 1

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ds = []
		ans = []
		self.f(0, target, candidates, ds, ans)
		return ans


class Solution:

	def combinationSum2(self, candidates, tar):

		def back(ind, arr, tar, ds, ans):
			if tar == 0:
				ans.append(ds[:])
				return
			for i in range(ind, len(arr)):
				if i > ind and arr[i] == arr[i - 1]:
					continue
				if arr[i] > tar:
					break
				ds.append(arr[i])
				back(i + 1, arr, tar - arr[i], ds, ans)
				ds.pop()
		ans = []
		ds = []
		candidates.sort()
		back(0, candidates, tar, ds, ans)
		return ans


class Solution:

	def helper(self, idx, tar, ar, ds, out):
		if tar == 0:
			out.append(list(ds))
			return
		for i in range(idx, len(ar)):
			if i > idx and ar[i] == ar[i - 1]:
				continue
			if ar[i] > tar:
				break
			ds.append(ar[i])
			self.helper(i + 1, tar - ar[i], ar, ds, out)
			ds.pop()

	def combinationSum2(self, candidates, target):
		out = []
		candidates.sort()
		self.helper(0, target, candidates, [], out)
		return out


class Solution:

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

	def combinationSum2(self, candidates, target):
		ans = []
		candidates.sort()
		self.findComb(0, candidates, [], ans, target)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		p = sorted(candidates)
		res = []
		op1 = []
		start = 0
		self.comb(start, res, op1, target, p)
		return res

	def comb(self, start, res, op1, t, p):
		if t == 0:
			res.append(op1.copy())
		if t <= 0:
			return
		prev = -1
		for i in range(start, len(p)):
			if p[i] == prev:
				continue
			op1.append(p[i])
			self.comb(i + 1, res, op1, t - p[i], p)
			op1.pop()
			prev = p[i]


class Solution:

	def combinationSum2(self, candidates, target):
		ans = []
		N = len(candidates)
		candidates.sort()

		def helper(i, target, temp):
			if target == 0:
				ans.append(temp.copy())
				return
			for index in range(i, N):
				if index > i and candidates[index] == candidates[index - 1]:
					continue
				elif candidates[index] > target:
					break
				else:
					temp.append(candidates[index])
					helper(index + 1, target - candidates[index], temp)
					temp.pop()
		helper(0, target, [])
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		ans = []
		candidates.sort()

		def fun(i, res, t):
			if t == 0:
				ans.append(res[:])
				return
			for j in range(i, len(candidates)):
				if j > i and candidates[j] == candidates[j - 1]:
					continue
				if t < candidates[i]:
					break
				res.append(candidates[j])
				t -= candidates[j]
				fun(j + 1, res, t)
				res.pop()
				t += candidates[j]
		fun(0, [], target)
		return ans


class Solution:

	def findcom(self, ind, t, c, ds, ans):
		if t == 0:
			ans.append(ds[:])
			return
		for i in range(ind, len(c)):
			if i > ind and c[i] == c[i - 1]:
				continue
			if c[i] > t:
				break
			ds.append(c[i])
			self.findcom(i + 1, t - c[i], c, ds, ans)
			ds.pop()

	def combinationSum2(self, candidates, target):
		ans = []
		self.findcom(0, target, sorted(candidates), [], ans)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		candidates.sort()
		ans = []
		self.fn(candidates, target, ans, [], 0)
		return ans

	def fn(self, candidates, target, ans, elems, index):
		if target == 0:
			ans.append(elems)
			return
		for i in range(index, len(candidates)):
			if i > index and candidates[i] == candidates[i - 1]:
				continue
			if candidates[i] > target:
				break
			self.fn(candidates, target - candidates[i], ans, elems + [candidates[i]], i + 1)


class Solution:

	def combinationSum2(self, candidates, target):

		def dfs(idx, path, cur):
			if cur > target:
				return
			if cur == target:
				if path:
					ans.append(path)
				return
			for i in range(idx, len(candidates)):
				if i > idx and candidates[i] == candidates[i - 1]:
					continue
				dfs(i + 1, path + [candidates[i]], cur + candidates[i])
		candidates.sort()
		n = len(candidates)
		ans = []
		dfs(0, [], 0)
		return sorted(ans)