寻求Rust实现符合特定规则的组合生成算法方案

这是典型的**回溯（深度优先搜索）**问题，核心是通过递归尝试所有符合规则的数字组合，同时利用"非递增"规则剪枝，避免无效尝试。

伪代码实现 #

// 主函数：生成所有符合条件的组合
generate_combinations(target):
    result = []
    // 初始调用：当前和为0，路径为空，允许的最大数字为4（规则2）
    backtrack(0, [], 4, target, result)
    return result

// 回溯辅助函数
backtrack(current_sum, current_path, max_num, target, result):
    // 终止条件1：当前和等于目标值，记录组合
    if current_sum == target:
        add a copy of current_path to result
        return
    // 终止条件2：当前和超过目标值，直接返回
    if current_sum > target:
        return
    // 从max_num往下遍历到1，保证组合非递增
    // 同时限制num不超过剩余需要的和，避免无用尝试
    for num from min(max_num, 4, target - current_sum) down to 1:
        // 选择当前数字
        add num to current_path
        // 递归：下一层的最大数字只能是当前num，保证非递增
        backtrack(current_sum + num, current_path, num, target, result)
        // 回溯：撤销选择
        remove num from current_path

Rust 代码实现 #

fn generate_combinations(target: u32) -> Vec<Vec<u32>> {
    let mut result = Vec::new();
    let mut current_path = Vec::new();
    backtrack(0, &mut current_path, 4, target, &mut result);
    result
}

fn backtrack(
    current_sum: u32,
    current_path: &mut Vec<u32>,
    max_num: u32,
    target: u32,
    result: &mut Vec<Vec<u32>>,
) {
    if current_sum == target {
        // 保存路径副本，避免后续修改影响结果
        result.push(current_path.clone());
        return;
    }
    if current_sum > target {
        return;
    }
    // 计算当前可选的最大数字：不超过max_num、4、剩余需要的和
    let upper = std::cmp::min(max_num, std::cmp::min(4, target - current_sum));
    // 从大到小遍历，保证组合非递增
    for num in (1..=upper).rev() {
        current_path.push(num);
        backtrack(current_sum + num, current_path, num, target, result);
        // 回溯：弹出最后添加的数字
        current_path.pop();
    }
}

// 测试用例
fn main() {
    println!("输入3的结果：{:?}", generate_combinations(3));
    println!("输入6的结果：{:?}", generate_combinations(6));
}

关键逻辑说明 #

1. 非递增保证：每次递归时，下一层允许的最大数字是当前选择的数字，后续添加的数字只会小于等于当前数字，自然满足非递增规则。
2. 剪枝优化：通过upper限制遍历的最大数字，避免尝试超过剩余和的数字，减少无效递归。
3. Rust 细节：用clone()保存路径副本，借助Vec的push和pop实现回溯，完全符合Rust的所有权规则，无需GC管理内存。

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