39. Combination Sum

Problem: https://leetcode.cn/problems/combination-sum/description/

Find all unique combinations of candidates where the chosen numbers sum to target. The same number may be used a unlimited number of times.

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        sort(candidates.begin(), candidates.end());
        int n = candidates.size();
        vector<int> current;
        
        function<void(int, int)> backtrack = [&](int start, int remaining) {
            if (remaining == 0) {
                result.push_back(current);
                return;
            }
            if (start == n || remaining < candidates[start]) {
                return;
            }
            // iterate over the candidates starting from 'start'
            for (int i = start; i < n; ++i) {
                if (remaining < candidates[i]) break;
                current.push_back(candidates[i]);
                backtrack(i, remaining - candidates[i]);  // allow reuse
                current.pop_back();
            }
        };
        
        backtrack(0, target);
        return result;
    }
};

Key points:

• Sorting helps prune when remaining < candidates[start].
• The recursive call uses index i (not i+1) because each number can be reused unlimited times.

40. Combination Sum II

Problem: https://leetcode.cn/problems/combination-sum-ii/description/

Each number in candidates may only be used once, and the solution set must not contain duplicate combinations.

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        vector<vector<int>> result;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        int n = candidates.size();
        
        function<void(int, int)> backtrack = [&](int start, int remaining) {
            if (remaining == 0) {
                result.push_back(current);
                return;
            }
            if (start == n || remaining < candidates[start]) {
                return;
            }
            for (int i = start; i < n; ++i) {
                // skip duplicates at the same recursion level
                if (i > start && candidates[i] == candidates[i-1]) continue;
                if (remaining < candidates[i]) break;
                current.push_back(candidates[i]);
                backtrack(i + 1, remaining - candidates[i]);
                current.pop_back();
            }
        };
        
        backtrack(0, target);
        return result;
    }
};

Key points:

• Sorting is required to group duplicates and enable pruning.
• i > start && candidates[i] == candidates[i-1] ensures no duplicate combinations on the same depth level.
• Each element is used only once, so recursion moves to i + 1.

131. Palindrome Partitioning

Problem: https://leetcode.cn/problems/palindrome-partitioning/description/

Given a string s, partition it into all possible palindrome substrings.

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

public:
    vector<vector<string>> partition(string s) {
        vector<vector<string>> result;
        vector<string> path;
        int n = s.size();
        
        function<void(int)> backtrack = [&](int start) {
            if (start == n) {
                result.push_back(path);
                return;
            }
            for (int end = start; end < n; ++end) {
                if (isPalindrome(s, start, end)) {
                    path.push_back(s.substr(start, end - start + 1));
                    backtrack(end + 1);
                    path.pop_back();
                }
            }
        };
        
        backtrack(0);
        return result;
    }
};

Key points:

• At each position, try to take a palindrome substring and recursively partition the remaining suffix.
• Palindrome check is performed inline using isPalindrome.
• Alternatively, one can use a "choose comma or not" approach but the above method is simpler.

All three problems follow the clasic backtracking pattern: explore, constrain, prune, and backtrack.