递归实现三元方程x1+x2+x3=num的解统计与输出问题求助

First, let's break down the key issues with your current code and fix them with a more efficient, practical recursive approach:

1. Core Problems in Your Current Code #

Exponential Complexity (3^n) #

Your code branches into three recursive calls every time (incrementing x1, x2, or x3), leading to an enormous number of redundant operations. For values like num=30, this would generate trillions of recursive calls—completely impossible to run in reasonable time.

Practicality Over Correctness #

While your code might count valid solutions correctly for small num (like 5), the exponential growth makes it unusable for larger values. You mentioned "duplicate counting," but that's likely not the case—each triplet is visited exactly once. The real pain point is the sheer number of unnecessary recursive calls.

2. The Fix: Ordered Recursive Traversal #

Instead of branching into all three variables at once, we can use a sequential recursive approach: first iterate through valid values of x1, then for each x1, iterate through valid values of x2, and compute x3 directly (since x3 = num - x1 - x2). We only count the solution if x3 falls within 1-10.

This reduces complexity to O(10*10) = 100 recursive calls at most—way more efficient. Here's the implementation:

public static int solutions(int num) {
    if (num < 3 || num > 30) return 0;
    // Start with x1=1, x2=1; x3 is derived from num-x1-x2
    return countSolutions(num, 1, 1);
}

private static int countSolutions(int num, int x1, int x2) {
    int count = 0;
    int x3 = num - x1 - x2;

    // Check if x3 is within the valid 1-10 range
    if (x3 >= 1 && x3 <= 10) {
        System.out.println(x1 + " + " + x2 + " + " + x3);
        count++;
    }

    // First, increment x2 until it reaches 10
    if (x2 < 10) {
        count += countSolutions(num, x1, x2 + 1);
    }
    // When x2 hits 10, increment x1 and reset x2 to 1 (if x1 hasn't hit 10)
    else if (x1 < 10) {
        count += countSolutions(num, x1 + 1, 1);
    }

    return count;
}

How This Works #

• We start with x1=1 and x2=1. For each pair (x1, x2), we calculate x3 and check if it's valid.
• We recursively increment x2 from 1 to 10 for the current x1.
• Once x2 reaches 10, we increment x1 by 1 and reset x2 to 1, repeating until x1 reaches 10.
• This ensures we only iterate through every valid (x1, x2) pair exactly once, with no redundant branches.

Testing with num=5 #

This code will output exactly the 6 valid triplets and return 6, as expected:

1 + 1 + 3
1 + 2 + 2
1 + 3 + 1
2 + 1 + 2
2 + 2 + 1
3 + 1 + 1

3. Alternative Recursive Approach (Variable-by-Variable) #

If you prefer a more explicit "choose one variable at a time" recursion, here's another version that first selects x1, then x2, then validates x3:

public static int solutions(int num) {
    if (num < 3 || num > 30) return 0;
    return countX1(num, 1);
}

// Recursively iterate x1 from 1 to 10
private static int countX1(int num, int x1) {
    if (x1 > 10) return 0;
    return countX2(num, x1, 1) + countX1(num, x1 + 1);
}

// For each x1, iterate x2 from 1 to 10
private static int countX2(int num, int x1, int x2) {
    if (x2 > 10) return 0;
    int x3 = num - x1 - x2;
    int count = (x3 >= 1 && x3 <= 10) ? 1 : 0;
    if (count == 1) {
        System.out.println(x1 + " + " + x2 + " + " + x3);
    }
    return count + countX2(num, x1, x2 + 1);
}

Both approaches eliminate exponential complexity and ensure you only process valid pairs once, making the code practical even for num=30.

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