153. Combination Sum II

Description

Given an array num and a number target. Find all unique combinations in num where the numbers sum to target.

Each number in num can only be used once in one combination.

All numbers (including target) will be positive integers.

Numbers in a combination a1, a2, … , ak must be in non-descending order. (ie, a1 ≤ a2 ≤ … ≤ ak)

Different combinations can be in any order.

The solution set must not contain duplicate combinations.

Example

Example 1:

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

Output: [[1,1,6],[1,2,5],[1,7],[2,6]]

Example 2:

Input: num = [1,1,1], target = 2

Output: [[1,1]]

Explanation: The solution set must not contain duplicate combinations

思路：

和135题类似，不同的是不能使用一个元素多次，所以start_index要变成 i + 1，也不需要用set去掉重复元素，其他基本没差。

代码：