Solution For Combination Sum Ii

Problem Statement:

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.

Example:

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

Output:

Solution:

This problem is a variation of the classic combination sum problem where we need to find all unique combinations of a set of numbers that add up to a given target. We can use the same approach as the combination sum problem to solve this problem as well. However, we need to add an additional check to ensure that no duplicate combinations are generated.

The approach we will take is a recursive backtracking approach. We will start with an empty array as the current combination, and we will add numbers to this combination one at a time. At each step, we will check if the current combination adds up to the target. If it does, we will add it to the list of valid combinations. If not, we will continue exploring all possible combinations that can be formed with the remaining numbers, taking care to avoid adding duplicate combinations.

Here are the steps to implement this algorithm:

1. Sort the input array in ascending order. This will ensure that duplicates are adjacent to each other.

2. Initialize an empty list to hold all valid combinations.

3. Define a recursive function called backtrack that takes as input the current combination, the remaining numbers to consider, and the target.

4. If the current combination adds up to the target, add it to the list of valid combinations. Otherwise, continue exploring all possible combinations that can be formed with the remaining numbers.

5. To avoid duplicate combinations, we will skip over any numbers that are the same as the previous number we added to the current combination. This is because any combination that includes the first occurrence of a duplicate will be the same as a combination that includes the second occurrence of the duplicate.

6. Call the backtrack function with an empty array as the current combination, the entire input array as the remaining numbers to consider, and the target as the target sum.

7. Return the list of valid combinations.

Here is the Python 3 code for the solution:

“`
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
# Step 1: Sort the input array in ascending order
candidates.sort()

    # Step 2: Initialize an empty list to hold all valid combinations
    result = []

    # Step 3: Define the recursive backtrack function
    def backtrack(curr_combination, remaining_nums, target_sum):
        # Base case: If the target sum is reached, add the current combination to the result list
        if target_sum == 0:
            result.append(curr_combination)
            return

        # Recursive case: Explore all possible combinations that can be formed with the remaining numbers
        for i in range(len(remaining_nums)):
            # Skip over duplicates to avoid generating duplicate combinations
            if i > 0 and remaining_nums[i] == remaining_nums[i-1]:
                continue

            # If the current number is larger than the remaining target sum, skip it
            if remaining_nums[i] > target_sum:
                break

            # Recursively get all combinations that can be formed with the remaining numbers
            backtrack(curr_combination + [remaining_nums[i]], remaining_nums[i+1:], target_sum - remaining_nums[i])

    # Step 4: Call the backtrack function with an empty array as the current combination, the entire input array as the remaining numbers to consider, and the target as the target sum
    backtrack([], candidates, target)

    # Step 7: Return the list of valid combinations
    return result

“`

Time Complexity:

The time complexity of this algorithm is O(2^n), where n is the length of the input array. In the worst case, every number in the input array can be included or excluded from the combination. However, the actual time complexity will be lower than this because we skip over duplicates and numbers that are larger than the target sum.

Space Complexity:

The space complexity of this algorithm is O(n), where n is the length of the input array. This is the maximum amount of extra space that can be used to store the current combination at any point in the algorithm.

Step by Step Implementation For Combination Sum Ii

class Solution {
    public List> combinationSum2(int[] candidates, int target) {
        List> result = new ArrayList<>();
        // sort the array first
        Arrays.sort(candidates);
        backtrack(result, new ArrayList<>(), candidates, target, 0);
        return result;
    }
    
    private void backtrack(List> result, List tempList, int [] candidates, int remain, int start){
        if(remain < 0) return;
        else if(remain == 0) result.add(new ArrayList<>(tempList));
        else{ 
            for(int i = start; i < candidates.length; i++){
                // if current element is equal to the previous element, then skip it to avoid duplicates
                if(i > start && candidates[i] == candidates[i-1]) continue;
                tempList.add(candidates[i]);
                // not passing i here since we can use same element multiple times
                backtrack(result, tempList, candidates, remain - candidates[i], i + 1);
                tempList.remove(tempList.size() - 1); 
            }
        }
    }
}

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        candidates.sort()
        result = []
        self.combine_sum_2(candidates, target, 0, [], result)
        return result
    
    def combine_sum_2(self, candidates, target, index, path, result):
        if target == 0:
            result.append(path)
            return
        
        for i in range(index, len(candidates)):
            if i > index and candidates[i] == candidates[i-1]:
                continue
            if target < candidates[i]:
                break
            self.combine_sum_2(candidates, target-candidates[i], i+1, path+[candidates[i]], result)

var combinationSum2 = function(candidates, target) {
    candidates.sort((a,b) => a-b);
    let result = [];
    let dfs = (target, start, temp) => {
        if (target === 0) {
            result.push(temp);
            return;
        }
        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] === candidates[i-1]) continue;
            if (target < candidates[i]) break;
            dfs(target - candidates[i], i + 1, [...temp, candidates[i]]);
        }
    }
    dfs(target, 0, []);
    return result;
};

vector> combinationSum2(vector& candidates, int target) {
    vector> res;
    vector curr;
    sort(candidates.begin(), candidates.end());
    backtrack(res, curr, candidates, target, 0);
    return res;
}

void backtrack(vector>& res, vector& curr, vector& candidates, int target, int start) {
    if (target == 0) {
        res.push_back(curr);
        return;
    }
    for (int i = start; i < candidates.size() && target >= candidates[i]; ++i) {
        if (i > start && candidates[i] == candidates[i-1]) {  // skip duplicates
            continue;
        }
        curr.push_back(candidates[i]);
        backtrack(res, curr, candidates, target-candidates[i], i+1);
        curr.pop_back();
    }
}

public class Solution {
    public IList> CombinationSum2(int[] candidates, int target) {
        // create a list to store all the combinations
        IList> combinations = new List>();
        
        // sort the candidates array
        Array.Sort(candidates);
        
        // call the backtracking function to find all the combinations
        FindCombinations(candidates, target, 0, new List(), combinations);
        
        return combinations;
    }
    
    public void FindCombinations(int[] candidates, int target, int index, List current, IList> combinations)
    {
        // if the target is reached, add the current combination to the list
        if(target == 0)
        {
            combinations.Add(new List(current));
            return;
        }
        
        // iterate through the array starting from the given index
        for(int i = index; i < candidates.Length; i++)
        {
            // if the current element is greater than the target, break the loop
            if(candidates[i] > target)
            {
                break;
            }
            
            // if the current element is equal to the previous element, continue to the next element
            if(i > index && candidates[i] == candidates[i-1])
            {
                continue;
            }
            
            // add the current element to the combination and call the function again with the remaining target
            current.Add(candidates[i]);
            FindCombinations(candidates, target - candidates[i], i + 1, current, combinations);
            current.RemoveAt(current.Count - 1);
        }
    }
}