# Leetcode 40. Combination Sum II

## 題解

### DFS + Sorting + Binary Search

利用 sorting 和 Binary Search 先把大於 target 的數字排除掉，然後 DFS Back Tracking

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        def sort(left: int, right: int, nums: List[int]):
            if left >= right:
                return
            i = left
            j = right
            pivot = left
            while i < j:
                while nums[j] > nums[pivot] and i < j:
                    j -= 1
                while nums[i] <= nums[pivot] and i < j:
                    i += 1
                nums[i],nums[j] = nums[j],nums[i]
            nums[i],nums[pivot] = nums[pivot],nums[i]
            sort(left,i - 1,nums)
            sort(i + 1,right,nums)

        def binary_search(nums: List[int], target: int):
            left = 0
            right = len(nums) - 1
            ans = 0
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] <= target:
                    left = mid + 1
                    ans = left
                else:
                    right = mid - 1
            return ans
        
        sort(0,len(candidates) - 1,candidates)
        right_bound = binary_search(candidates, target) # 利用 Binary Search 找到大於 target 數字的邊界
        candidates = candidates[:right_bound]
        n = len(candidates)
        output = []

        def dfs(start:int,sums: int, ans: List[int]):
            if sums > target:
                return
            if sums == target:
                output.append(ans[:])
            else:
                for i in range(start,n):
                    if i > start and candidates[i] == candidates[i-1]: continue # 排除重複組合
                    c = candidates[i]
                    ans.append(c)
                    dfs(i+1,sums + c, ans)
                    ans.pop()
        dfs(0,0,[])
        return output