Combination Sum (Problem 39)

Given a distinct integer array candidates and a target value target, find all unique combinations in candidates where the numbers sum to target. Each number may be used repeatedly.

The solution uses backtracking with these key components:

• Parameters: The recursive function tracks the current sum, path, and starting index to avoid duplicate combinations.
• Base Cases: Terminate when the current sum equals or exceeds the target.
• Recursive Logic: Iterate from the starting index. Since reuse is allowed, pass the same index (i) to the next recursion.

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtrack(vector<int>& nums, int target, int currentSum, int start) {
        if (currentSum == target) {
            result.push_back(path);
            return;
        }
        if (currentSum > target) return;

        for (int i = start; i < nums.size() && currentSum + nums[i] <= target; ++i) {
            path.push_back(nums[i]);
            backtrack(nums, target, currentSum + nums[i], i);
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        backtrack(candidates, target, 0, 0);
        return result;
    }
};

Combination Sum II (Problem 40)

Given an integer array candidates (with duplicates) and a target target, find all unique combinations where each number is used at most once per combination.

Key differences from Problem 39:

• Each element can only be used once → increment index to i+1 in recursion.
• Input may contain duplicates → skip duplicates at the same decision level (tree layer), not within the same path (tree branch).

To handle duplicates:

1. Sort the input array.
2. Use a used array to track whether an element was used in the current branch.
3. Skip candidates[i] if it equals candidates[i-1] and used[i-1] is false (indicating a tree-layer duplicate).

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;

    void backtrack(vector<int>& nums, int target, int currentSum, int start, vector<bool>& used) {
        if (currentSum == target) {
            result.push_back(path);
            return;
        }

        for (int i = start; i < nums.size() && currentSum + nums[i] <= target; ++i) {
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) 
                continue;

            path.push_back(nums[i]);
            used[i] = true;
            backtrack(nums, target, currentSum + nums[i], i + 1, used);
            used[i] = false;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<bool> used(candidates.size(), false);
        backtrack(candidates, target, 0, 0, used);
        return result;
    }
};

Palindrome Partisioning (Problem 131)

Given a string s, partition it such that every substring is a palindrome. Return all possible partitions.

This problem models string segmentation as a backtracking tree:

• Each recursive level chooses a cut point i starting from startIndex.
• The substring s[startIndex..i] must be a palindrome to proceed.
• If valid, add it to the current path and recurse starting at i+1.

A helper function checks palindromes using two pointers:

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

Main backtracking logic:

class Solution {
private:
    vector<vector<string>> result;
    vector<string> path;

    void backtrack(const string& s, int start) {
        if (start == s.length()) {
            result.push_back(path);
            return;
        }

        for (int i = start; i < s.length(); ++i) {
            if (isPal(s, start, i)) {
                path.push_back(s.substr(start, i - start + 1));
                backtrack(s, i + 1);
                path.pop_back();
            }
        }
    }

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

public:
    vector<vector<string>> partition(string s) {
        backtrack(s, 0);
        return result;
    }
};