Java编程逻辑问题：求用1~k的数组成total的组合数

Hey there! Let's break down what's going wrong with your current code and how to fix it with backtracking (or even a more efficient dynamic programming approach).

What's Wrong with Your Current Code #

Your approach tries to build combinations by merging adjacent 1s, but this strategy misses valid combinations that don't come from merging adjacent elements. For example, when total=6 and k=3, your code would miss the combination 2+2+2 because your merging logic doesn't account for splitting the original 1s into multiple non-adjacent pairs. This method simply can't cover all possible valid combinations.

Backtracking Solution #

The key to solving this problem correctly is to generate combinations in a way that avoids duplicates and covers all possibilities. Since combinations are unordered (e.g., 1+2+2 is the same as 2+1+2), we can enforce a rule: each next number we choose must be greater than or equal to the last one we picked. This ensures we only generate unique, non-decreasing combinations.

Here's a Java implementation using backtracking:

public class CombinationCounter {
    public static void main(String[] args) {
        System.out.println(countCombinations(5, 3)); // Output: 5
        System.out.println(countCombinations(6, 3)); // Output: 6
    }

    private static int countCombinations(int total, int k) {
        // Start backtracking with current sum 0, and the smallest possible number (1)
        return backtrack(0, 1, total, k);
    }

    private static int backtrack(int currentSum, int start, int total, int k) {
        int count = 0;
        // Iterate from 'start' to k (to maintain non-decreasing order)
        for (int i = start; i <= k; i++) {
            int newSum = currentSum + i;
            if (newSum == total) {
                // We found a valid combination
                count += 1;
            } else if (newSum < total) {
                // Recurse with the new sum, and start from i (to avoid duplicates)
                count += backtrack(newSum, i, total, k);
            } else {
                // Since i is increasing, further numbers will be larger, so break early
                break;
            }
        }
        return count;
    }
}

How this works:

• The backtrack function takes the current sum of our combination, the smallest number we can pick next (to enforce non-decreasing order), the target total, and k.
• For each number from start to k:
  • If adding it to the current sum equals the total, we increment our count.
  • If it's less than the total, we recurse with the new sum and keep the start as the current number (so we don't pick smaller numbers later, avoiding duplicates like 2+1).
  • If it exceeds the total, we break the loop immediately—since all larger numbers will also exceed the total.

Dynamic Programming Alternative #

If you're dealing with large values of total, backtracking can be slow due to repeated recursive calls. A dynamic programming approach is more efficient, with a time complexity of O(total * k):

public class CombinationCounter {
    public static void main(String[] args) {
        System.out.println(countCombinationsDP(5, 3)); // Output: 5
        System.out.println(countCombinationsDP(6, 3)); // Output: 6
    }

    private static int countCombinationsDP(int total, int k) {
        int[] dp = new int[total + 1];
        dp[0] = 1; // Base case: there's 1 way to make sum 0 (using no numbers)
        
        // For each number from 1 to k
        for (int num = 1; num <= k; num++) {
            // Update dp[i] for all sums from num to total
            for (int i = num; i <= total; i++) {
                dp[i] += dp[i - num];
            }
        }
        return dp[total];
    }
}

How this works:

• dp[i] represents the number of ways to get the sum i using numbers from 1 to k.
• We initialize dp[0] = 1 because there's exactly one way to get sum 0 (choosing nothing).
• For each number num, we iterate through all sums from num to total, and add the number of ways to get i - num to dp[i]—this accounts for adding num to all combinations that sum to i - num.

Both approaches will correctly count all valid combinations. The backtracking method is intuitive and easy to understand, while the dynamic programming method is better for larger values of total due to its efficiency.

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