40. Combination Sum II

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 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]
]

Constraints:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

Approach 01:

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        ranges::sort(candidates);
        dfs(candidates, 0, target, {}, result);
        return result;
    }

private:
    void dfs(const vector<int>& A, int s, int target, vector<int>&& path, vector<vector<int>>& result) {
        if (target < 0){
            return;
        }            
        if (target == 0) {
            result.push_back(path);
            return;
        }

        for (int i = s; i < A.size(); ++i) {
            if (i > s && A[i] == A[i - 1])
                continue;
            path.push_back(A[i]);
            dfs(A, i + 1, target - A[i], move(path), result);
            path.pop_back();
        }
    }
};

from typing import List

class Solution:
    def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
        result = []
        candidates.sort()
        self.dfs(candidates, 0, target, [], result)
        return result

    def dfs(self, A: List[int], s: int, target: int, path: List[int], result: List[List[int]]):
        if target < 0:
            return
        if target == 0:
            result.append(path[:])  # Append a copy of path
            return

        for i in range(s, len(A)):
            if i > s and A[i] == A[i - 1]:
                continue
            path.append(A[i])
            self.dfs(A, i + 1, target - A[i], path, result)
            path.pop()

Time Complexity

• Sorting:

  The initial sorting of the candidates array takes \( O(n \log n) \) time, where \( n \) is the number of elements in the array.

• DFS Traversal:

  The depth-first search (DFS) explores all possible combinations. In the worst case, it explores all subsets of the candidates array, which can be \( O(2^n) \) in the number of recursive calls.

• Overall Time Complexity:

  The overall time complexity is \( O(n \log n + 2^n) \), where the dominant factor is \( O(2^n) \) due to the DFS traversal.

Space Complexity

• Auxiliary Space:

  The auxiliary space used by the recursive call stack is determined by the maximum depth of the recursion, which is \( O(n) \). Additionally, the space for the path vector is also \( O(n) \) in the worst case.

• Overall Space Complexity:

  The overall space complexity is \( O(n) \), mainly due to the recursion stack and the path vector.