如何生成满足求和范围约束的排列（避免全量生成）

Great question! The brute-force expand.grid approach works fine for small datasets, but it quickly hits performance walls when dealing with large or numerous sets—this is exactly where pruned recursive backtracking shines. It lets you generate only the valid combinations without ever creating the full cartesian product. Let’s break down how to implement this in R, with logic that scales much better.

Core Pruning Logic #

The key insight is to dynamically check if a partial combination can still lead to a valid sum before you finish building it. Here’s the rule:

• Suppose you’ve already selected elements summing to current_sum, and you have k sets left to pick from.
• Calculate min_remaining (sum of the smallest elements in each remaining set) and max_remaining (sum of the largest elements in each remaining set).
• If current_sum + max_remaining < lower_bound: Even picking the largest possible elements from the remaining sets won’t reach the minimum sum—abandon this branch.
• If current_sum + min_remaining > upper_bound: Even picking the smallest possible elements from the remaining sets will exceed the maximum sum—abandon this branch.

We can also add a pre-pruning step to remove elements that can never be part of any valid combination, regardless of what other elements you pick. For example, your set1 element 10: even when combined with the largest elements from set2 and set3 (9+4=13), the total is 23, which is below your lower bound of 25. We can safely remove 10 upfront to reduce our workload.

R Implementation #

Let’s turn this logic into code. First, a function to pre-prune individual sets:

# Pre-prune a single set by removing elements that can't contribute to any valid combination
prune_single_set <- function(single_set, other_sets, lower, upper) {
  min_other_total <- sum(sapply(other_sets, min))
  max_other_total <- sum(sapply(other_sets, max))
  
  # Keep elements where:
  # x + smallest possible sum from other sets <= upper bound, AND
  # x + largest possible sum from other sets >= lower bound
  single_set[single_set + min_other_total <= upper & single_set + max_other_total >= lower]
}

Next, a recursive function that builds combinations and prunes invalid branches on the fly:

# Recursively generate valid combinations with dynamic pruning
generate_valid_combinations <- function(sets, lower, upper, current_sum = 0, current_comb = c()) {
  # Base case: all sets have been processed
  if (length(sets) == 0) {
    if (current_sum >= lower && current_sum <= upper) {
      return(list(current_comb))
    } else {
      return(list())
    }
  }
  
  current_set <- sets[[1]]
  remaining_sets <- sets[-1]
  
  # Calculate bounds for remaining sets to guide pruning
  min_remaining <- sum(sapply(remaining_sets, min))
  max_remaining <- sum(sapply(remaining_sets, max))
  
  # Filter elements in current set that could lead to a valid combination
  valid_elements <- c()
  # Sorting the set lets us break early (optional but efficient)
  sorted_set <- sort(current_set)
  for (x in sorted_set) {
    new_sum <- current_sum + x
    
    # If even the smallest possible total from here is too big, break (since set is sorted)
    if (new_sum + min_remaining > upper) {
      break
    }
    # If the largest possible total from here is still too small, skip
    if (new_sum + max_remaining < lower) {
      next
    }
    
    valid_elements <- c(valid_elements, x)
  }
  
  # Recurse on each valid element
  results <- list()
  for (x in valid_elements) {
    sub_results <- generate_valid_combinations(
      remaining_sets,
      lower,
      upper,
      current_sum + x,
      c(current_comb, x)
    )
    results <- c(results, sub_results)
  }
  
  return(results)
}

Test with Your Example #

Let’s apply this to your original data:

# Original sets
set1 <- c(10, 15, 20)
set2 <- c(8, 9)
set3 <- c(1, 2, 3, 4)
all_sets <- list(set1, set2, set3)
lower_bound <- 25
upper_bound <- 29

# Step 1: Pre-prune all sets
pruned_sets <- list()
for (i in seq_along(all_sets)) {
  pruned_sets[[i]] <- prune_single_set(all_sets[[i]], all_sets[-i], lower_bound, upper_bound)
}
# pruned_sets[[1]] is now c(15, 20) — the invalid 10 is gone!

# Step 2: Generate valid combinations
valid_combs <- generate_valid_combinations(pruned_sets, lower_bound, upper_bound)

# Convert to a data frame for readability (matches your original output)
final_df <- do.call(rbind, lapply(valid_combs, function(comb) {
  data.frame(
    Var1 = comb[1],
    Var2 = comb[2],
    Var3 = comb[3],
    sum = sum(comb)
  )
}))

print(final_df)

This will output exactly the same rows as your original final data frame, but without generating all 324=24 combinations first.

Why This Works Better #

• No full cartesian product: We only generate combinations that have a shot at meeting the sum constraint. For large sets, this can reduce computation from millions of rows to thousands or less.
• Dual pruning: Pre-pruning removes obvious invalid elements upfront, and dynamic pruning stops useless recursive branches early.
• Scalable: This approach handles more sets or larger individual sets far better than expand.grid, since the pruning logic keeps the number of active branches manageable.

内容的提问来源于stack exchange，提问作者C. Braun