Problem 216: Combination Sum III

Description: Given two integers k and n, find all possible combinations of k numbers from 1 to 9 that add up to n. Each number can only be used once in a combination.

Approach

This problem requires finding subsets of size k from the set [1,2,3,4,5,6,7,8,9] where the sum equals n. The parameter k represents the depth of the recursion tree, while the fixed set size (9 elements) determines the breadth.

For example, if k = 2 and n = 4, we need to find all pairs of distinct numbers from 1-9 that sum to 4: [1,3].

Backtracking Template

Recurtion Parameters

• path: A one-dimensional vector storing the current combination
• result: A two-dimensional vector storing all valid combinations
• targetSum: The target sum (n from the problem)
• k: Required size of combination
• currentSum: Sum of elements in current path
• startIndex: Starting index for next level iteration

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    
    void backtrack(int targetSum, int k, int currentSum, int startIndex) {
        if (path.size() == k) {
            if (currentSum == targetSum) {
                result.push_back(path);
            }
            return;
        }
        
        for (int i = startIndex; i <= 9; i++) {
            currentSum += i;
            path.push_back(i);
            backtrack(targetSum, k, currentSum, i + 1);
            currentSum -= i;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtrack(n, k, 0, 1);
        return result;
    }
};

Pruning Optimization

Two pruning strategies can significantly reduce unnecessary exploration:

1. Early termination: If current sum exceeds target, stop exploring
2. Loop bounds: Limit the upper bound of the for loop based on remaining elements needed

For the loop bounds optimization:

• Remaining positions to fill: k - path.size()
• Maximum value to iterate: 9 - (k - path.size()) + 1

class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    
    void backtrack(int targetSum, int k, int currentSum, int startIndex) {
        // Pruning: early termination if sum exceeds target
        if (currentSum > targetSum) {
            return;
        }
        
        if (path.size() == k) {
            if (currentSum == targetSum) {
                result.push_back(path);
            }
            return;
        }
        
        // Pruning: optimize loop bounds
        int upperBound = 9 - (k - path.size()) + 1;
        for (int i = startIndex; i <= upperBound; i++) {
            currentSum += i;
            path.push_back(i);
            backtrack(targetSum, k, currentSum, i + 1);
            currentSum -= i;
            path.pop_back();
        }
    }

public:
    vector<vector<int>> combinationSum3(int k, int n) {
        result.clear();
        path.clear();
        backtrack(n, k, 0, 1);
        return result;
    }
};

Problem 17: Letter Combinations of a Phone Number

Description: Given a string containing digits from 2 to 9, return all possible letter combinations that the number could represent. The mapping follows a standard telephone keypad:

Example: Input: "23" → Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Approach

This problem can be visualized as an n-level tree where n is the length of the input digit string. Each level corresponds to one digit, and each node at that level represents choosing one letter from the available options for that digit.

The tree depth equals digits.length(), and each leaf node represents a complete letter combination.

Digit-to-Letter Mapping

const string mapping[10] = {
    "",     // 0
    "",     // 1
    "abc",  // 2
    "def",  // 3
    "ghi",  // 4
    "jkl",  // 5
    "mno",  // 6
    "pqrs", // 7
    "tuv",  // 8
    "wxyz"  // 9
};

Backtracking Template

Recursion Parameters

• result: Vector storing all valid letter combinations
• combination: String storing current combination
• digits: Input digit string
• depth: Current position in the digit string (also represents tree depth)

Note: Unlike the previous combination problem where we use startIndex, this problem uses depth to track position in the input string.

class Solution {
private:
    const string mapping[10] = {
        "",     // 0
        "",     // 1
        "abc",  // 2
        "def",  // 3
        "ghi",  // 4
        "jkl",  // 5
        "mno",  // 6
        "pqrs", // 7
        "tuv",  // 8
        "wxyz"  // 9
    };
    
public:
    vector<string> result;
    string combination;
    
    void backtrack(const string& digits, int depth) {
        if (depth == digits.length()) {
            result.push_back(combination);
            return;
        }
        
        int digit = digits[depth] - '0';
        const string& letters = mapping[digit];
        
        for (char c : letters) {
            combination.push_back(c);
            backtrack(digits, depth + 1);
            combination.pop_back();
        }
    }
    
    vector<string> letterCombinations(string digits) {
        combination.clear();
        result.clear();
        
        if (digits.empty()) {
            return result;
        }
        
        backtrack(digits, 0);
        return result;
    }
};

Key Differences from Combination Problems

1. Different collection types: Problem 77 and Problem 216 select from a single set with startIndex, while Problem 17 processes different sets at each level
2. Loop starting point: In letter combinations, the loop always starts from index 0 (all letters for that digit), not a starting index
3. Edge cases: Consider handling invalid input like "1", "*", or "#" in production code

Complexity Analysis

• Time complexity: O(4^n × n) where n is the length of digits (worst case: all digits are 7 or 9 with 4 letters each)
• Space complexity: O(n) for recursion depth, excluding output storage