LeetCode

Appearance

40. 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 sum to target.

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

Note: The solution set must not contain duplicate combinations.

 

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output: 
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output: 
[
[1,2,2],
[5]
]

 

Constraints:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30
Related Topics
  • 数组
  • 回溯

  • 👍 1684
  • 👎 0

    • 思路 ​

    回溯算法，需要处理重复元素，需要先对数组进行排序，方便跳过重复元素。

    判断条件为： 若 candidate[i - 1] 在 path 中， 则 candidate[i] 也可以进入path

    若前者不在 path 中，说明已经处理过这个元素

    解法 ​

    py
    # leetcode submit region begin(Prohibit modification and deletion)

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        res = []

        def backtrack(path, total, used, start):
            if total == target:
                res.append(path[:])
                return
            if total > target:
                return


            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1] and not used[i - 1]:
                    continue

                if not used[i]:
                    used[i] = True
                    path.append(candidates[i])
                    backtrack(path, total + candidates[i], used, i + 1)
                    path.pop()
                    used[i] = False



        backtrack([], 0, [False] * len(candidates), 0)

        return res

        
# leetcode submit region end(Prohibit modification and deletion)

    复杂度分析 ​

    • 时间复杂度 O(2^n)
    • 空间复杂度 O(N)