Combination Sum II

Leetcode Problem:

• Combination Sum II

Summary

• Find all unique combinations in candidates where the candidate numbers sum to target.

Approach

• Depth-First Search (DFS) with backtracking, utilizing a counter array to track the availability of each candidate number.

Complexity

• O(N * target), where N is the number of candidates

Explain

• The solution uses a DFS approach with backtracking to explore all possible combinations
• It maintains a counter array to track the availability of each candidate number
• The dfs function recursively tries to add each candidate number to the current combination, and backtracks if the sum exceeds the target or if the candidate number is no longer available
• The solution also ensures that duplicate combinations are not included by using a history array to keep track of the candidate numbers added to the current combination.

Solution Code:

class Solution {
public:
    int cnt[31];
    void dfs(vector>& ans, vector& history, int cur, int sum, int target){
        if(sum == target){
            vector tmp;
            for(int i = 0 ; i < history.size(); i++){
                tmp.push_back(history[i]);
            }
            ans.push_back(tmp);
            return;
        }
        if (sum > target) return;

        for(int i = cur; i <= target; i++){
            if(cnt[i] <= 0) continue;
            cnt[i]--;
            history.push_back(i);
            dfs(ans, history, i, sum + i, target);
            cnt[i]++;
            history.pop_back();
        }
    }
    vector> combinationSum2(vector& candidates, int target) {
        for(int i = 0 ; i < candidates.size(); i++){
            if (candidates[i] > 30) continue;
            cnt[candidates[i]]++;
        }
        vector> ans;
        vector history;
        dfs(ans, history, 0, 0, target);
        return ans;
    }
};