40. Combination Sum II

Description

The problem requires finding all unique combinations of numbers from a given list (candidates) that sum up to a specified target. Each number in the list can be used only once in each combination. The solution set should not contain duplicate combinations, and the combinations can be in any order.

Intuition

To solve the problem, we can use a backtracking approach to explore all possible combinations. Sorting the array helps in easily skipping duplicate elements, which is essential to avoid duplicate combinations in the result set.

Approach

1. Sorting: Start by sorting the candidates array. This allows us to easily skip over duplicate elements and helps in efficiently pruning the search space.
2. Backtracking: Implement a recursive backtracking function that: - Adds the current combination to the result list when the target sum is reached. - Recursively explores adding each subsequent number in the sorted list to the current combination. - Skips over any duplicate numbers to ensure each combination is unique. - Stops exploring further when the current sum exceeds the target.
3. Pruning: Since the array is sorted, if the current sum exceeds the target at any point, further recursion can be terminated early to save computation.

Complexity

Time Complexity:

O(2^n), where n is the number of elements in the candidates list. This is due to the backtracking approach, which can potentially explore all subsets.

Space Complexity:

O(n), where n is the number of elements in the candidates list. This space is used by the recursion stack and the current combination path.

Code

C++

class Solution {
public:
    vector> combinationSum2(vector& candidates, int target) {
        vector> result;
        vector path;
        sort(candidates.begin(), candidates.end());
        backtracking(result, path, candidates, target, 0, 0);
        return result;
    }

private:
    void backtracking(vector>& result, vector& path, vector& candidates, int target, int start, int sum) {
        if (sum == target) {
            result.push_back(path);
            return;
        }

        for (int i = start; i < candidates.size(); ++i) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            if (sum + candidates[i] > target) break;

            path.push_back(candidates[i]);
            backtracking(result, path, candidates, target, i + 1, sum + candidates[i]);
            path.pop_back();
        }
    }
};

Python

class Solution:
    def combinationSum2(self, candidates, target):
        result = []
        candidates.sort()
        
        def backtracking(path, start, sum):
            if sum == target:
                result.append(path[:])
                return

            for i in range(start, len(candidates)):
                if i > start and candidates[i] == candidates[i - 1]:
                    continue
                if sum + candidates[i] > target:
                    break

                path.append(candidates[i])
                backtracking(path, i + 1, sum + candidates[i])
                path.pop()
        
        backtracking([], 0, 0)
        return result

Java

class Solution {
    public List> combinationSum2(int[] candidates, int target) {
        List> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtracking(result, new ArrayList<>(), candidates, target, 0, 0);
        return result;
    }

    private void backtracking(List> result, List path, int[] candidates, int target, int start, int sum) {
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1]) continue;
            if (sum + candidates[i] > target) break;

            path.add(candidates[i]);
            backtracking(result, path, candidates, target, i + 1, sum + candidates[i]);
            path.remove(path.size() - 1);
        }
    }
}

JavaScript

var combinationSum2 = function (candidates, target) {
    
    let result = []
    candidates.sort((a, b) => a - b)
    console.log(candidates)
    let backtraking = (path, start, sum) => {
        if (sum === target) {
            result.push(path.slice())
            return
        }

        for (let i = start; i < candidates.length; i++) {
            if (i > start && candidates[i] == candidates[i - 1])
                continue
            if (sum > target)
                break

            path.push(candidates[i])
            backtraking(path, i + 1, sum+candidates[i])
            path.pop()
        }
    }
    backtraking([], 0, 0)
    return result
};