leetcode40. Combination Sum II

原题地址https://leetcode.com/problems/combination-sum-ii/

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]
]

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        
        def backtrack(addup, path, candidates):
            if addup == 0:
                res.append(path[:])
            for i, num in enumerate(candidates):
                if num > addup:
                    break
                if i ==0 or candidates[i] != candidates[i-1]: 
                    path.append(num)
                    backtrack(addup-num, path, candidates[i+1:])
                    path.pop()
        res = []
        path = []
        backtrack(target, path, candidates)
        return res

if i ==0 or candidates[i] != candidates[i-1]: 

重复数字在第一次遇到时进行遍历，后面可以直接跳过。
假设在排序后candidates为[1,1,1,2,2,...]，第一次遇到1时@，加入到path中，path=[1]，在1已经归入到path中后,我们还需要在下一级的函数中继续遍历1后面的数字[1,1,...]。那么我们会得到[1,1,1...],[1,1,2..]。

那么在@处是否还需要继续遍历同级遍历中已经出现的1呢？
假如我们遍历第二个1，下一级中我们需要继续遍历[1,2,2,...]，得到[1,1,2..]，与@处得到的[1,1,2]重复了，不符合题意，所以需要跳过。

所有排列组合题我刚开始想学习到同一个套路，一次性解决，但是每次都会遇到意想不到的问题，做这题之前，感觉没法用一个套路消化掉，但是解决这题后感觉我又可以了。诀窍还是要画图，不管使用树的形式还是什么别的形式，把遍历情况写出来，然后观察什么样的枝是需要剪掉的，嗯看是很难一步到位的。图后面再补吧。