Files
2020-08-07 17:06:53 +08:00

49 lines
1.4 KiB
Markdown
Executable File
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

# [40. 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]
]
## 题目大意
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
## 解题思路
- 题目要求出总和为 sum 的所有组合,组合需要去重。这一题是第 39 题的加强版,第 39 题中元素可以重复利用(重复元素可无限次使用),这一题中元素只能有限次数的利用,因为存在重复元素,并且每个元素只能用一次(重复元素只能使用有限次)
- 这一题和第 47 题类似,只不过元素可以反复使用。