[Leetcode] Combination Sum II

An extension of Combination Sum. The point is when and how to prun.

Description

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.

Examples

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

Solution

To avoid reduntant usage of same index, put index as a parameter in dfs and increment it when forwarding the recursion. Use this parameter to check if restraint is violated and thus return.

The difficult part is when array contains multiple same elements, elms with different index may also cause duplication. To avoid this, only one of indices of elms with same val can be forwarded to dfs. In the loop check if curr val equals to prev val and continue to next loop without trigering dfs if they’re same.

Note the situation of including both same elms would not be filtered, as this occurs when i has been incremented in deeper level of dfs, and j equals to i here, preventing the filtration from executing.

• code

ref: https://blog.csdn.net/fuxuemingzhu/article/details/79343638