#
# [40] Combination Sum II
#
# https://leetcode.com/problems/combination-sum-ii/description/
#
# algorithms
# Medium (35.45%)
# Total Accepted:    142.3K
# Total Submissions: 401.2K
# Testcase Example:  '[10,1,2,7,6,1,5]\n8'
#
# 
# Given a collection of candidate numbers (C) and a target number (T), find all
# unique combinations in C where the candidate numbers sums to T.
# 
# 
# Each number in C 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.
# 
# 
# 
# 
# For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, 
# A solution set is: 
# 
# [
# ⁠ [1, 7],
# ⁠ [1, 2, 5],
# ⁠ [2, 6],
# ⁠ [1, 1, 6]
# ]
# 
# 
#
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates = sorted(candidates)
        self.backtracking(candidates, target, res, [], 0)
        return res
    def backtracking(self, candidates, target, res ,temp, start):
        if target < 0:
            return
        elif target == 0:
            res.append(list(temp))
        else:
            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i-1]:
                    continue
                temp.append(candidates[i])
                # can use mutilple
                self.backtracking(candidates, target - candidates[i], res, temp, i+1)
                temp.pop()
                
        
