如何用递归编写高效Java程序求0-3中3个数和为5的可重复排列

Hey there! Let's tackle this problem step by step. The goal is to generate all permutations of 3 numbers (each ranging from 0 to 3) that add up to 5, while making the recursive code more efficient and cutting down on messy if checks.

Key Optimization Strategies #

First, let's outline the fixes to boost efficiency and clean up the code:

• Early Pruning: Cut off recursive branches that can't possibly lead to a valid result, instead of letting them run to completion.
• Replace Hardcoded Checks with Loops: Use a loop to iterate through the valid number range (0-3) instead of writing separate if conditions for each digit.
• Track Remaining Sum: Keep track of how much sum we still need to reach the target as we recurse, avoiding redundant sum calculations at the end.
• Reusable Path Storage: Use a single array to build the current permutation, reducing memory overhead from repeated object creation.

Optimized Recursive Code #

Here's the revised implementation that follows these strategies:

import java.util.ArrayList;
import java.util.List;

public class PermutationsSum {
    public static void main(String[] args) {
        int targetSum = 5;
        int permutationLength = 3;
        int minDigit = 0;
        int maxDigit = 3;
        
        List<String> result = new ArrayList<>();
        generateValidPermutations(0, new int[permutationLength], targetSum, minDigit, maxDigit, result);
        
        // Print results in the required format
        System.out.println(String.join("、", result));
    }
    
    private static void generateValidPermutations(
            int currentPosition, 
            int[] currentPath, 
            int remainingSum, 
            int minDigit, 
            int maxDigit, 
            List<String> result) {
        
        // Termination: we've filled all positions in the permutation
        if (currentPosition == currentPath.length) {
            if (remainingSum == 0) {
                // Convert the path array to the required string format
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < currentPath.length; i++) {
                    if (i > 0) sb.append(" + ");
                    sb.append(currentPath[i]);
                }
                result.add(sb.toString());
            }
            return;
        }
        
        int remainingPositions = currentPath.length - currentPosition - 1;
        
        // Iterate through all valid digits instead of hardcoding checks
        for (int digit = minDigit; digit <= maxDigit; digit++) {
            int newRemainingSum = remainingSum - digit;
            // Calculate the possible sum range for remaining positions
            int minPossibleRemainingSum = minDigit * remainingPositions;
            int maxPossibleRemainingSum = maxDigit * remainingPositions;
            
            // Prune invalid branches: skip if remaining sum can't be achieved with remaining positions
            if (newRemainingSum >= minPossibleRemainingSum && newRemainingSum <= maxPossibleRemainingSum) {
                currentPath[currentPosition] = digit;
                // Recurse to fill the next position
                generateValidPermutations(currentPosition + 1, currentPath, newRemainingSum, minDigit, maxDigit, result);
            }
        }
    }
}

How This Works #

• Early Pruning: For each digit we consider, we check if subtracting it from the remaining sum leaves a value that can be achieved with the remaining empty positions (using digits 0-3). If not, we skip that digit entirely, avoiding unnecessary recursive calls.
• Cleaner Code: The loop over minDigit to maxDigit replaces any hardcoded if checks for individual digits, making the code easier to modify (e.g., if you want to change the digit range later).
• Efficient Sum Tracking: By passing the remaining sum instead of recalculating the sum of the current path each time, we save computation time.
• Memory Efficiency: Reusing the currentPath array instead of creating new collections for each recursion reduces memory churn.

When you run this code, it will output exactly the format you need:
3 + 2 + 0、3 + 1 + 1、3 + 0 + 2、2 + 2 + 1、2 + 1 + 2、2 + 0 + 3、1 + 3 + 1、1 + 2 + 2、1 + 1 + 3

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