Combination Sum III

Find all valid combinations of k distinct numbers from 1 to 9 that sum to a target value n.

A backtracking approach is used with two pruning strategies:

1. Skip further exploration if the current sum exceeds n.
2. Limit the loop range to ensure enough remaining numbers are available to complete the combination.

class Solution {
    vector<vector<int>> results;
    vector<int> current;

    void backtrack(int target, int count, int start, int currentSum) {
        if (currentSum > target) return;
        if (current.size() == count && currentSum == target) {
            results.push_back(current);
            return;
        }

        for (int num = start; num <= 9 - (count - current.size()) + 1; ++num) {
            current.push_back(num);
            backtrack(target, count, num + 1, currentSum + num);
            current.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        backtrack(n, k, 1, 0);
        return results;
    }
};

A alternative pruning condition inside the loop (currentSum + num <= n) can also be applied for early termination.

Letter Combinations of a Phone Number

Given a string of digits from 2–9, generate all possible letter combinations based on the traditional phone keypad mapping.

The solution uses backtracking to explore all character choices for each digit:

class Solution {
    const string mappings[10] = {
        "", "", "abc", "def", "ghi", "jkl",
        "mno", "pqrs", "tuv", "wxyz"
    };

    vector<string> combinations;
    string currentStr;

    void generate(const string& digits, int pos) {
        if (pos == digits.length()) {
            combinations.push_back(currentStr);
            return;
        }

        int digit = digits[pos] - '0';
        const string& letters = mappings[digit];
        for (char c : letters) {
            currentStr.push_back(c);
            generate(digits, pos + 1);
            currentStr.pop_back();
        }
    }

public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        generate(digits, 0);
        return combinations;
    }
};