Python函数修改求助：获取所有和为目标值的数字组合并筛选最短组合

Let's break down your problem and fix the function step by step. Your current implementation only returns the first valid combination it finds (and has some critical issues with mutable default parameters), so we'll rebuild it to first collect all possible valid combinations, then pick the shortest one.

First: Understand the Flaws in Your Current Code #

Your existing bestSum has three key problems that prevent it from working as intended:

1. Mutable default parameter: res=[[], []] is initialized once when the function is defined, not on each call. This means recursive calls share the same list, leading to unexpected state leaks and incorrect results.
2. Early return: As soon as it finds one valid combination, it returns immediately—so it never checks other potential combinations that might be shorter.
3. Limited data structure: The res variable can only hold one combination, not a collection of all valid paths through your binary tree logic.

Step 1: Build a Function to Return All Valid Combinations #

First, let's create an allSum function that recursively collects every possible combination of numbers that add up to the target. This follows your original binary tree approach, but we'll keep track of all valid paths instead of stopping at the first one:

def allSum(target, nums, memo=None):
    # Initialize memoization dictionary on first call (avoids mutable default issues)
    if memo is None:
        memo = {}
    
    # Return cached result if we've already computed this target
    if target in memo:
        return memo[target]
    
    # Base case: target is 0, return a list containing an empty list (valid combination found)
    if target == 0:
        return [[]]
    
    # Base case: target is negative, no valid combinations exist
    if target < 0:
        return []
    
    all_combinations = []
    for num in nums:
        remainder = target - num
        # Recursively find all combinations for the remainder
        remainder_combinations = allSum(remainder, nums, memo)
        # Prepend the current number to each remainder combination to form valid paths
        current_combinations = [[num] + combo for combo in remainder_combinations]
        # Add these combinations to our total list
        all_combinations.extend(current_combinations)
    
    # Cache the result for future calls to optimize performance
    memo[target] = all_combinations
    return all_combinations

Testing this with your example:

print(allSum(7, [5,3,4,7]))
# Output: [[3, 4], [4, 3], [7]]

And for the case with no solution:

print(allSum(7, [4,5]))
# Output: []

Step 2: Extract the Shortest Combination #

Now that we have all valid combinations, we can build the bestSum function to filter for the shortest one(s):

def bestSum(target, nums):
    all_combinations = allSum(target, nums)
    
    # If no valid combinations exist, return None
    if not all_combinations:
        return None
    
    # Find the length of the shortest combination
    shortest_length = min(len(combo) for combo in all_combinations)
    # Collect all combinations that match this shortest length (in case of ties)
    shortest_combinations = [combo for combo in all_combinations if len(combo) == shortest_length]
    
    # Return a single shortest combination (or return the full list if you want all ties)
    return shortest_combinations[0]

Testing this with your example:

print(bestSum(7, [5,3,4,7]))
# Output: [7]

Key Improvements #

• Memoization: The allSum function uses memoization to avoid redundant calculations, making it much faster for larger targets or number lists.
• No mutable defaults: We initialize the memo dictionary inside the function to prevent state leaks between calls.
• Full combination collection: We don't stop at the first valid path—we collect all possible combinations, then pick the shortest one, which ensures you get the optimal result every time.

内容的提问来源于stack exchange，提问作者MMEL