0039.求和.md

39. 求和

题目链接

C++

// 本题使用回溯算法
#include <bits/stdc++.h>
using namespace std;
 
int n, m;
 
vector<vector<int>> ans; // 用来储存所有答案

void backtracking(vector<int>& path, int n, int target, int cur, int sum) {
    // 如果sum == target说明达成目标
    // 将符合的组合加入ans中
    if(sum == target) {
        ans.push_back(path);
        return;
    }
    for(int i = cur; i <= n; ++i) {
        // 暂且把i加上
        sum += i;
        path.push_back(i);
        // 这里cur的位置一定要填i + 1, 否则会重复计算且可能超时
        backtracking(path, n, target, i + 1, sum);
        // 撤销刚刚的操作
        sum -= i;
        path.pop_back();
    }
}
 
void solve() {
    vector<int> path; // 用来储存可行的某一种答案
    backtracking(path, n, m, 1, 0);
    // 输出数据
    for(int i = 0; i < ans.size(); ++i) {
        for(auto j : ans[i]) {
            printf("%d ", j);
        }
        printf("\n");
    }
}
 
int main()
{
    while(cin >> n >> m) {
        solve();
    }
    return 0;
}

Java

/**
 * 思路：回溯算法
 * 
 * 确定递归函数的参数列表
 * 
 *   backtracking(int index, int sum)
 *   index: 用于标记当前编辑到数的位置
 *   sum: 当前累积的和
 * 
 * 终止条件
 * 
 *   当 sum 大于所需要的值时就终止
 * 
 * 遍历方式：
 *   
 *   按照树形结构的遍历方式进行遍历
 */

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    static ArrayList<Integer> list; // 用于存储当前组合的列表
    static int m, n; // 目标和 m 和范围 n

    // 回溯函数，index 是当前要考虑的数字，sum 是当前组合的和
    static void backtracking(int index, int sum) {
        if (sum > m) {
            return; // 如果当前和已经大于目标和，返回，不再继续搜索
        }
        if (sum == m) {
            // 如果当前和等于目标和，打印当前组合
            for (int i = 0; i < list.size() - 1; i++) {
                System.out.print(list.get(i) + " ");
            }
            System.out.println(list.get(list.size() - 1));
        }
        for (int i = index; i <= n && sum + i <= m; i++) {
            // 从当前数字开始尝试添加到组合中
            list.add(i); // 添加当前数字到组合中
            backtracking(i + 1, sum + i); // 递归搜索下一个数字
            list.remove(list.size() - 1); // 回溯，将当前数字移出组合
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // while (scanner.hasNext()) {
            n = scanner.nextInt();
            m = scanner.nextInt();
            list = new ArrayList<>();
            backtracking(1, 0); // 从第一个数字开始搜索
            list.clear(); // 清空组合列表，准备下一次循环
        // }
    }
}

Python

###################
# 问题：求和
###################

# 思路：组合问题，使用回溯进行解决

def huisu(res, path, start, nums, m):
    if sum(path) == m:
        res.append(path.copy())
        return
    if start >= len(nums):
        return
    for i in range(start, len(nums)):
        path.append(nums[i])
        huisu(res=res, path=path, start=i+1, nums=nums, m=m)
        path.pop()
     

n, m = map(int, input().split(" "))
nums = [x for x in range(1, n+1)]
res = []
path = []
huisu(res=res, path=path, start=0, nums=nums, m=m)
for i in res:
    tmp = ""
    for k in range(len(i)):
        if k!=len(i)-1:
            tmp += str(i[k]) + " "
        else:
            tmp += str(i[k])
    print(tmp)

Go

JS

C