This problem can be solved using a technique called backtracking. Here are the steps to solve this problem:

1. First, sort the array of candidates. This will help to avoid duplicates and to stop the recursion early.

2. Create a function, let's call it `backtrack`, that will take the current combination, the sum of the current combination, and the start position for the next candidate.

3. In the `backtrack` function, check if the sum of the current combination is equal to the target. If it is, add the current combination to the result and return.

4. If the sum of the current combination is greater than the target, return without adding the current combination to the result. This is because, since the candidates are sorted, if the current combination exceeds the target, any further combinations will also exceed the target.

5. If the sum of the current combination is less than the target, iterate over the candidates starting from the start position. For each candidate, add it to the current combination and call `backtrack` with the new combination, the new sum, and the next position as the start position. This is because each number in candidates may only be used once in the combination.

6. After calling `backtrack` for a candidate, remove it from the current combination to backtrack.

7. To avoid duplicates, if a candidate is the same as the previous candidate, skip it.

8. Finally, call `backtrack` with an empty combination, a sum of 0, and a start position of 0 to start the process.

Here is a Python solution for the problem:

```python
def combinationSum2(candidates, target):
def backtrack(comb, start, target):
if target == 0:
result.append(list(comb))
return
for i in range(start, len(candidates)):
if i start and candidates[i] == candidates[i-1]:
continue
if candidates[i] target:
break
comb.append(candidates[i])
backtrack(comb, i+1, target-candidates[i])
comb.pop()
candidates.sort()
result = []
backtrack([], 0, target)
return result
```

You can call the function with the candidates and the target as arguments, like this:

```python
print(combinationSum2([10,1,2,7,6,1,5], 8))
print(combinationSum2([2,5,2,1,2], 5))
```

This will print:

```
[[1,1,6],[1,2,5],[1,7],[2,6]]
[[1,2,2],[5]]
```

which are the expected outputs.

Question

This problem can be solved using a technique called backtracking. Here are the steps to solve this problem:

1. First, sort the array of candidates. This will help to avoid duplicates and to stop the recursion early.

2. Create a function, let's call it `backtrack`, that will take the current combination, the sum of the current combination, and the start position for the next candidate.

3. In the `backtrack` function, check if the sum of the current combination is equal to the target. If it is, add the current combination to the result and return.

4. If the sum of the current combination is greater than the target, return without adding the current combination to the result. This is because, since the candidates are sorted, if the current combination exceeds the target, any further combinations will also exceed the target.

5. If the sum of the current combination is less than the target, iterate over the candidates starting from the start position. For each candidate, add it to the current combination and call `backtrack` with the new combination, the new sum, and the next position as the start position. This is because each number in candidates may only be used once in the combination.

6. After calling `backtrack` for a candidate, remove it from the current combination to backtrack.

7. To avoid duplicates, if a candidate is the same as the previous candidate, skip it.

8. Finally, call `backtrack` with an empty combination, a sum of 0, and a start position of 0 to start the process.

Here is a Python solution for the problem:

```python
def combinationSum2(candidates, target):
    def backtrack(comb, start, target):
        if target == 0:
            result.append(list(comb))
            return
        for i in range(start, len(candidates)):
            if i > start and candidates[i] == candidates[i-1]:
                continue
            if candidates[i] > target:
                break
            comb.append(candidates[i])
            backtrack(comb, i+1, target-candidates[i])
            comb.pop()
    candidates.sort()
    result = []
    backtrack([], 0, target)
    return result
```

You can call the function with the candidates and the target as arguments, like this:

```python
print(combinationSum2([10,1,2,7,6,1,5], 8))
print(combinationSum2([2,5,2,1,2], 5))
```

This will print:

```
[[1,1,6],[1,2,5],[1,7],[2,6]]
[[1,2,2],[5]]
```

which are the expected outputs.

Knowee AI · Accepted Answer