Combination Sum II | Leetcode : 40 | Medium | Using Recursion and Backtracking | Easy to Solve

If you are diving into the world of coding challenges, you might have encountered the "Combination Sum II" problem on LeetCode. This problem is not just about finding combinations but ensuring they are unique. In this blog post, we will explore how to solve this problem effectively, dissect the solution, and understand its time and space complexity in a better Way.

Problem Overview

The Combination Sum II problem asks you to find all unique combinations in a list of numbers that sum up to a specific target. Each number in the list can only be used once, and the solution must avoid duplicate combinations.

Example 1:

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

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

Example 2:

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

  [
    [1,2,2],
    [5]
  ]

C++ Code :-

    class Solution {

    public:

        void solve(vector<int>& candidates, int target, vector<int> v,

                    vector<vector<int>> &ans, int index) {

            if (target == 0) {

                ans.push_back(v);

                return;

            }

            if (target < 0)

                return;

            for (int i = index; i < candidates.size(); i++) {

                // Skip duplicates

                if (i > index && candidates[i] == candidates[i - 1])

                    continue;

                // Include the current number and explore further

                v.push_back(candidates[i]);

                solve(candidates, target - candidates[i], v, ans, i + 1);

               

                // Backtrack to explore other possibilities

                v.pop_back();

            }

        }

        vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {

            sort(candidates.begin(), candidates.end());  // Sort the candidates

            vector<int> v;  // Current combination

            vector<vector<int>> ans;  // To store all valid combinations

            solve(candidates, target, v, ans, 0);  // Start backtracking

            return ans;

        }

    };

   

How It Works

1. Sorting the Candidates:

   • The candidates vector is sorted initially with sort(candidates.begin(), candidates.end()). This sorting helps in easily skipping duplicates later on.

2. Recursive Backtracking Function (solve):

   • Base Case: When target is 0, it means the current combination v adds up to the desired target. Hence, v is added to ans.
   • Early Termination: If target becomes negative, it means the current path is invalid, so the function returns early.
   • Iterating and Skipping Duplicates: The loop starts from index to avoid recombination and skips over duplicates using if (i > index && candidates[i] == candidates[i - 1]) continue;.
   • Exploring New Combinations: The current number is added to the combination (v.push_back(candidates[i])), and the function recursively explores further possibilities by calling solve with the updated target and index.
   • Backtracking: After exploring the current path, the last added number is removed (v.pop_back()) to backtrack and explore other combinations.

3. Main Function (combinationSum2):

   • Initializes the combination vector v and the result vector 'ans'.
   • Calls "solve" with the initial parameters to start the backtracking process.
   • Returns the 'ans' vector containing all unique combinations that sum up to the target.

Time and Space Complexity

Time Complexity:

• The time complexity of this algorithm is $O(2^N)$, where $N$ is the number of candidates. This is because, in the worst case, the algorithm explores all possible subsets of the input list. Although the exact number of calls depends on the specific input, it’s exponential in the number of candidates.

Space Complexity:

• The space complexity is $O(N)$ for storing the current combination v and the recursive call stack. In the worst case, the depth of the recursion tree can go up to $N$ (the length of the candidates array), and the space required to store the current combination can also be $O(N)$.

This solution effectively handles the "Combination Sum II" problem by utilizing sorting and backtracking to ensure all unique combinations are found without duplication. The approach is optimal for the problem constraints and efficiently manages the search space through careful pruning and duplication handling.

Keywords: Combination Sum II, C++ solution, coding interview, backtracking algorithm, unique combinations, time complexity, space complexity, Leetcode 40 solution, Leetcode 40 cpp solution, Leetcode 40 c++ solution, Leetcode 40 detailed solution, Leetcode Daily Practice, Leetcode Contest Solution