216. Combination Sum III

Problem Description

Find all unique combinations of k numbers from 1 to 9 that sum up to n. Each number can be used at most once.

Solution: Backtracking with Pruning

This problem can be efficiently solved using backtracking with pruning. The backtracking approach explores all possible combinations by recursively adding numbers to a current combination. Pruning helps to avoid unnecessary computations by eliminating branches that cannot lead to a valid solution.

Algorithm

1. dfs(index, currentSum, combination): This recursive function explores combinations starting from index.

   • Base Cases:
     • If currentSum equals n and the length of combination is k, a valid combination is found. Add it to the result and return.
     • If currentSum exceeds n or the length of combination exceeds k, this branch cannot lead to a valid solution. Return.
   • Recursive Step:
     • Iterate from index to 9 (inclusive). For each number i:
       • Add i to the combination.
       • Recursively call dfs(i + 1, currentSum + i, combination). i + 1 ensures that each number is used at most once.
       • Remove i from the combination (backtracking).

2. Main Function: Initialize an empty result list and call dfs(1, 0, []) to start the search.

Code (Python)

def combinationSum3(k, n):
    """
    Finds all valid combinations of k numbers that sum up to n.
 
    Args:
        k: The number of elements in each combination.
        n: The target sum.
 
    Returns:
        A list of lists, where each inner list represents a valid combination.
    """
    result = []
 
    def dfs(index, current_sum, combination):
        if current_sum == n and len(combination) == k:
            result.append(combination.copy())  # Add a copy to avoid modification
            return
        if current_sum > n or len(combination) > k:
            return
 
        for i in range(index, 10):  # Iterate from index to 9
            combination.append(i)
            dfs(i + 1, current_sum + i, combination)  # Explore next number
            combination.pop()  # Backtrack
 
    dfs(1, 0, [])
    return result
 

Time and Space Complexity Analysis

• Time Complexity: O(9!), which is exponential. In the worst case, the algorithm explores all possible combinations.
• Space Complexity: O(k), dominated by the depth of the recursion stack (the length of the combination list).

Alternative Solution: Bit Manipulation

A more concise solution can be achieved using bit manipulation. Each bit in a 9-bit integer represents the inclusion (1) or exclusion (0) of a number from 1 to 9.

Algorithm

1. Iterate through all possible 9-bit integers (0 to 511).
2. Check if the number of set bits (1s) in the integer equals k.
3. Calculate the sum of numbers corresponding to the set bits.
4. If the sum equals n, add the combination to the result.

Code (Python)

def combinationSum3_bit(k, n):
    result = []
    for i in range(1 << 9):  # Iterate through all 9-bit integers
        combination = []
        count = 0
        total = 0
        for j in range(9):
            if (i >> j) & 1:  # Check if j-th bit is set
                count += 1
                total += j + 1
                combination.append(j + 1)
        if count == k and total == n:
            result.append(combination)
    return result

Time and Space Complexity Analysis

• Time Complexity: O(29), which is still exponential but better than the previous approach for larger values of k.
• Space Complexity: O(k)

Both solutions correctly solve the problem. The backtracking approach is generally more flexible and can be adapted to similar problems with different constraints more easily. The bit manipulation approach is more concise but is less intuitive and efficient only for specific problems like this where numbers are in a small, fixed range.