Combination Sum

Given a collection of distinct integers and a target value, identify all unique combinations where the chosen numbers sum to the target. Each candidate may be used an unlimited number of times.

The solution employs depth-first search with backtracking. First, sort the input array to facilitate pruning. During traversal, maintain a running remainder of the target. If the remainder reaches zero, the current combination is valid. Iterate from the current positino, recursively exploring each candidate while updating the remainder.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
        vector<vector<int>> combinations;
        vector<int> current;
        sort(nums.begin(), nums.end());
        dfs(nums, target, 0, current, combinations);
        return combinations;
    }

private:
    void dfs(vector<int>& nums, int remain, int pos, vector<int>& current, vector<vector<int>>& combinations) {
        if (remain == 0) {
            combinations.push_back(current);
            return;
        }
        for (int i = pos; i < nums.size() && nums[i] <= remain; ++i) {
            current.push_back(nums[i]);
            dfs(nums, remain - nums[i], i, current, combinations);
            current.pop_back();
        }
    }
};

Combination Sum II

Given a collection of integers that may contain duplicates and a target value, find all unique combinations where the chosen numbers sum to the target. Each number may only be used once in each combination.

After sorting the array, traverse using backtracking. To avoid duplicate combinations, skip elements that are identical to the previous element at the same recursion level. This ensures that duplicate values are only considered in subsequent tree branches, not within the same branch level.

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& nums, int target) {
        vector<vector<int>> combinations;
        vector<int> current;
        sort(nums.begin(), nums.end());
        backtrack(nums, target, 0, current, combinations);
        return combinations;
    }

private:
    void backtrack(vector<int>& nums, int remain, int start, vector<int>& current, vector<vector<int>>& combinations) {
        if (remain == 0) {
            combinations.push_back(current);
            return;
        }
        for (int i = start; i < nums.size() && nums[i] <= remain; ++i) {
            if (i > start && nums[i] == nums[i - 1]) continue;
            current.push_back(nums[i]);
            backtrack(nums, remain - nums[i], i + 1, current, combinations);
            current.pop_back();
        }
    }
};

Palindrome Partitioning

Given a string, partition it such that every substring of the partition is a palindrome. Return all possible palindrome partitioning schemes.

The approach treats the partitioning as a tree traversal problem. Starting from each position, expand to find all palindromic substrings beginning at that index. For each valid palindrome found, add it to the current partition and recursively process the remainder of the string.

class Solution {
public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> solutions;
        vector<string> segments;
        backtrack(s, 0, segments, solutions);
        return solutions;
    }

private:
    void backtrack(const string& s, int begin, vector<string>& segments, vector<vector<string>>& solutions) {
        if (begin == s.size()) {
            solutions.push_back(segments);
            return;
        }
        for (int end = begin; end < s.size(); ++end) {
            if (isPalindrome(s, begin, end)) {
                segments.push_back(s.substr(begin, end - begin + 1));
                backtrack(s, end + 1, segments, solutions);
                segments.pop_back();
            }
        }
    }

    bool isPalindrome(const string& s, int left, int right) {
        while (left < right) {
            if (s[left++] != s[right--]) return false;
        }
        return true;
    }
};