Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:


       All numbers (including target) will be positive integers.
       The solution set must not contain duplicate combinations.


Example 1:


Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]


Example 2:


Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Complete search

Starter code: class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        

Solutions:
class Solution:

	def combinationSum2(self, candidates, target):

		def dfs(i, val, path):
			while i < len(candidates):
				num = candidates[i]
				val_ = val + num
				path_ = path + [num]
				if val_ > target:
					return
				elif val_ == target:
					ans.append(path_)
					return
				dfs(i + 1, val_, path_)
				while i < len(candidates) - 1 and candidates[i] == candidates[i + 1]:
					i += 1
				i += 1
		candidates = sorted(candidates)
		ans = []
		dfs(0, 0, [])
		return ans


class Solution:

	def combinationSum2(self, candidates, target):
		if not candidates:
			return []
		result = []
		candidates.sort()
		self.dfs(result, [], 0, target, candidates)
		return result

	def dfs(self, result, combin, start, target, candidates):
		if target == 0:
			result.append([i for i in combin])
		else:
			for index in range(start, len(candidates)):
				if candidates[index] > target:
					break
				if index > start and candidates[index] == candidates[index - 1]:
					continue
				combin.append(candidates[index])
				self.dfs(result, combin, index + 1, target - candidates[index], candidates)
				combin.pop()


class Solution:

	def combinationSum2(self, nums, target):

		def dfs(a, i, target):
			for j in range(i, len(nums)):
				if target <= nums[j]:
					if target == nums[j]:
						ans.append(a + [nums[j]])
					break
				if i == j or nums[j] != nums[j - 1]:
					dfs(a + [nums[j]], j + 1, target - nums[j])
		ans = []
		nums.sort()
		dfs([], 0, target)
		return ans


class Solution:

	def combinationSum2(self, candidates, target):

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


class Solution:

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

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


class Solution:

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

		def combinationSumRecu(self, candidates, target, start, intermediate, result):
			if target == 0:
				result.append(list(intermediate))
			while start < len(candidates) and candidates[start] <= target:
				intermediate.append(candidates[start])
				combinationSumRecu(self, candidates, target - candidates[start], start + 1, intermediate, result)
				start += 1
				intermediate.pop()
				while start > 0 and start < len(candidates) and (candidates[start] == candidates[start - 1]):
					start += 1
		combinationSumRecu(self, sorted(candidates), target, 0, [], result)
		return result


class Solution:

	def combinationSum2(self, candidates, target):
		dp = [None] + [set() for i in range(target)]
		candidates.sort()
		for i in candidates:
			if i > target:
				break
			for j in range(target - i, 0, -1):
				dp[i + j] |= {_ + (i,) for _ in dp[j]}
			dp[i].add((i,))
		return list(dp[-1])


class Solution:

	def find(self, candidates, result, current, target, pos, num, current_num):
		if target == 0:
			temp = current[:]
			result.append(temp)
		else:
			for i in range(pos, len(candidates)):
				n = str(candidates[i])
				if candidates[i] > target or num[n] < current_num[n]:
					break
				if num[n] == current_num[n]:
					continue
				current.append(candidates[i])
				current_num[n] += 1
				self.find(candidates, result, current, target - candidates[i], i, num, current_num)
				value = current.pop()
				current_num[str(value)] -= 1

	def combinationSum2(self, candidates, target):
		result = []
		current = []
		candidates.sort()
		can = candidates[:]
		count = 0
		num = {}
		current_num = {}
		for i in range(len(candidates)):
			if i == 0 or candidates[i] != candidates[i - 1]:
				num[str(candidates[i])] = 1
				current_num[str(candidates[i])] = 0
				continue
			else:
				num[str(candidates[i])] += 1
				del can[i - count]
				count += 1
		self.find(can, result, current, target, 0, num, current_num)
		return result


class Solution:

	def combinationSum2(self, candidates, target):

		def produce(nums, target, current, output):
			if target == 0:
				output.append(list(current))
				return
			for (i, n) in enumerate(nums):
				if n > target:
					continue
				if i > 0 and nums[i] == nums[i - 1]:
					continue
				current.append(n)
				produce(nums[i + 1:], target - n, current, output)
				current.pop()
		output = []
		candidates.sort()
		produce(candidates, target, [], output)
		return output


class Solution:

	def combinationSum2(self, candidates, target):
		sortedCandidates = sorted(candidates)
		if len(candidates) == 0 or target < sortedCandidates[0]:
			return []
		if target == sortedCandidates[0]:
			return [[sortedCandidates[0]]]
		resultWith0 = self.combinationSum2(sortedCandidates[1:], target - sortedCandidates[0])
		nextIndex = 0
		while nextIndex < len(candidates) and sortedCandidates[nextIndex] == sortedCandidates[0]:
			nextIndex += 1
		resultNo0 = self.combinationSum2(sortedCandidates[nextIndex:], target)
		return [[sortedCandidates[0]] + item for item in resultWith0] + resultNo0


class Solution:

	def combinationSum2(self, candidates, target):

		def backtracing(nums, target, idx, path, ret):
			if not target:
				if path not in ret:
					ret.append(path)
			for i in range(idx, len(nums)):
				if nums[i] > target:
					break
				backtracing(nums, target - nums[i], i + 1, path + [nums[i]], ret)
		candidates.sort()
		ret = []
		backtracing(candidates, target, 0, [], ret)
		return ret


class Solution:

	def combinationSum2(self, candidates, target):

		def combination(candidates, k, target, res, result):
			for i in range(k, len(candidates)):
				if target == candidates[i]:
					temp = [j for j in res]
					temp.append(candidates[i])
					temp.sort()
					if temp not in result:
						result.append(temp)
					return
				elif target < candidates[i]:
					return
				else:
					res.append(candidates[i])
					combination(candidates, i + 1, target - candidates[i], res, result)
					res.pop()
		candidates.sort()
		res = []
		result = []
		combination(candidates, 0, target, res, result)
		return result


class Solution(object):

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

	def util(self, nums, target, result, temp):
		for i in range(len(nums)):
			if nums[i] == target and temp + [nums[i]] not in result:
				result.append(temp + [nums[i]])
			elif nums[i] < target:
				self.util(nums[i + 1:], target - nums[i], result, temp + [nums[i]])
		return