Combination Sum - II

Lecture 118:-  Combination Sum - II

The "Combination Sum II" problem is a variation of the original Combination Sum problem where each element in the input array can only be used once in a combination. In other words, you need to find all unique combinations of elements in the array that add up to the given target sum, without using the same element more than once.

Here's how you can approach the Combination Sum II problem using a recursive backtracking approach in Python:

pythonCopy code

def combination_sum_2(candidates, target): def backtrack(start, target, path): if target == 0: result.append(path[:]) return for i in range(start, len(candidates)): if i > start and candidates[i] == candidates[i - 1]: continue # Skip duplicates to avoid duplicate combinations if candidates[i] <= target: path.append(candidates[i]) backtrack(i + 1, target - candidates[i], path) path.pop() candidates.sort() result = [] backtrack(0, target, []) return result # Example usage candidates = [10, 1, 2, 7, 6, 5] target = 8 combinations = combination_sum_2(candidates, target) print(combinations)

In this example, the combination_sum_2 function takes a sorted list of candidates (positive integers) and a target sum as input. It uses a helper function backtrack to explore all possible combinations of unique elements that add up to the target sum. The function avoids using the same candidate more than once in a combination and skips duplicates to avoid duplicate combinations.

The backtrack function iterates through the candidates starting from a specified index (start). It adds candidates to the current path and recursively explores combinations that include the current candidate. If the target sum is reached, the current path is added to the result list.

The time complexity of this solution is similar to the original Combination Sum problem using backtracking. It can vary, but in the worst case, it can be exponential due to the branching factor of the recursion. Pruning techniques and optimizations, such as sorting and skipping duplicates, can help improve performance.

This solution ensures that only unique combinations are generated by skipping duplicate candidates and using each candidate only once.