algoadvance

Given an array 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:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example

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

Input: candidates = [2,5,2,1,2], target = 5
Output: [[1,2,2],[5]]

Clarifying Questions

1. Can the candidates array contain negative numbers? No, all numbers are positive integers.

2. Can the target number be zero? No, the target number will always be a positive integer.

3. Is the order of combinations in the output important? No, the order of combinations in the output is not important.

4. Can the candidates array contain duplicates? Yes, the array can contain duplicates, but the combinations must be unique.

Strategy

1. Sort the Array
   • Sorting helps us easily skip duplicate combinations and prune the search space for more efficient backtracking.
2. Backtracking
   • Use backtracking to generate combinations. If the target becomes zero, we store the current combination.
   • If the target becomes negative or we have processed all elements, we backtrack.
   • We skip duplicates during the generation of combinations to avoid the generation of identical combinations.
3. Base Conditions
   • If the target is zero, add the current combination to the result.
   • If the target is less than zero or we have exhausted the list, return without adding the combination.

Solution with Code

def combinationSum2(candidates, target):
    def backtrack(start, end, temp_list, target):
        if target == 0:
            res.append(temp_list[:])
            return
        if target < 0:
            return
        for i in range(start, end):
            if i > start and candidates[i] == candidates[i - 1]:
                continue
            temp_list.append(candidates[i])
            backtrack(i + 1, end, temp_list, target - candidates[i])
            temp_list.pop()

    candidates.sort()
    res = []
    backtrack(0, len(candidates), [], target)
    return res

# Example Usage
candidates = [10, 1, 2, 7, 6, 1, 5]
target = 8
print(combinationSum2(candidates, target)) # Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

Time Complexity

The overall time complexity is difficult to determine exactly due to the variable nature of backtracking, but we can provide an estimate:

• Sorting the candidates has a complexity of (O(n \log n)).
• The backtracking function generates all possible combinations, so in the worst case, it will explore 2^n combinations where n is the length of the candidates. Hence, the backtracking step has an approximate upper bound complexity of (O(2^n)).

Thus, the total estimated time complexity is (O(n \log n + 2^n)).

This time complexity can vary significantly based on the input size and the values of the target and candidates array.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?