Combination sum-2

Dec 18, 2024 • 5 mins read
Hero Image

Problem Overview

The problem on LeetCode titled "Combination Sum II" is a classic recursion and backtracking problem. The task is to find all unique combinations in a given array of numbers where the numbers sum up to a specific target. Each number in the array can only be used once in each combination, which makes it slightly more challenging than its counterpart, "Combination Sum."

Understanding the Problem

Given an array of candidate numbers (candidates) and a target number (target), we must identify all combinations of candidates where the sum is equal to the target. Each number in the array may only be used once in each combination. The solution should not include duplicate combinations.

  1. Input:

    • A list of integers candidates.
    • An integer target.

  2. Output:

    • A list of lists, with each list representing a valid combination.

  3. Example:

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

    Here, the sum of each sublist is 8, and no number is repeated in any combination.

Key DSA Concepts and Theory

Recursion

Recursion is a method where the solution to a problem depends on solutions to smaller instances of the same problem. This problem uses recursion to explore each candidate by including it in the combination or excluding it.

Backtracking

Backtracking involves choosing candidates and, if a condition is violated, stepping back and trying the next possible solution without choosing the current candidate. It is particularly useful when deciding on combination or permutation problems where elements must sum or align to achieve a particular state.

Sorting

Sorting the candidates is crucial to manage duplicate entries. By sorting, we can easily skip over duplicates during the search, ensuring that we only include unique combinations in our result.

Solution Approach

The solution can be achieved using recursion and backtracking:

  1. Sort the candidates: Begin by sorting the array. This helps to easily skip duplicates and manage combinations more efficiently.

  2. Recursive Backtracking: Implement a recursive function to build up candidates:

    • Base Case: If the target becomes zero, a valid combination is found.
    • Recursive Case:
      • Iterate over candidates.
      • Skip any candidate that repeats consecutively to avoid duplicates.
      • Recursive call with remaining candidates and reduced target value.
      • Backtrack by removing the candidate after checking.

Below are implementations in C++ and Java.

C++ Code

#include <vector>
#include <algorithm>

class Solution {
public:
    std::vector<std::vector<int>> combinationSum2(std::vector<int>& candidates, int target) {
        std::sort(candidates.begin(), candidates.end());
        std::vector<std::vector<int>> result;
        std::vector<int> current;
        backtrack(candidates, target, 0, current, result);
        return result;
    }
    
private:
    void backtrack(std::vector<int>& candidates, int target, int start, 
                   std::vector<int>& current, std::vector<std::vector<int>>& result) {
        if (target == 0) {
            result.push_back(current);
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) continue; // skip duplicates
            if (candidates[i] > target) break; // no need to try further

            current.push_back(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.pop_back(); // backtrack
        }
    }
};

Java Code

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }
    
    private void backtrack(int[] candidates, int target, int start, 
                           List<Integer> current, List<List<Integer>> result) {
        if (target == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue; // skip duplicates
            if (candidates[i] > target) break; // no need to try further

            current.add(candidates[i]);
            backtrack(candidates, target - candidates[i], i + 1, current, result);
            current.remove(current.size() - 1); // backtrack
        }
    }
}

Time and Space Complexity Analysis

Time Complexity

  • Sorting the candidates takes O(N log N).
  • The backtracking approach involves a search across all subsets, which in the worst case can generate 2^N possibilities.
  • Thus, the total time complexity is O(N log N) + O(2^N).

Space Complexity

  • The algorithm uses additional space for the recursion call stack and to store current combinations, leading to a space complexity of O(N).

Common Mistakes to Avoid

  1. Not Sorting the Array: Sorting is essential for skipping duplicates efficiently. Ensure the array is sorted before processing combinations.

  2. Handling Duplicates: Forgetting to skip duplicate entries will result in redundant combinations. Use the "i > start && candidates[i] == candidates[i - 1]" condition properly.

  3. Not Backtracking Correctly: Ensure to backtrack by removing the last candidate after exploring it.

Similar Problems on LeetCode

Additional Resources and References

This guide should serve to give a comprehensive understanding of the "Combination Sum II" problem and how to tackle it using efficient algorithms and data structure principles.