求和

[编程题]求和

热度指数：485 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,使其和等于 m，要求将其中所有的可能组合列出来。

输入描述:

输入两个正整数，n和m。
其中n,m均不大于10

输出描述:

按每个组合的字典序排列输出，每行输出一种组合。

示例1

输入

5 5

输出

1 4
2 3
5

算法知识视频讲解

牛客网薛洋

import java.util.Scanner;
import java.util.Stack;

public class Main {
    
    static int now;

    public static void dfs(Stack<Integer> stack, int begin, int m, int n) {
        
        if (now == m) {
            
            for (int num : stack) {
                System.out.printf("%s ",num);
            }
            System.out.println();
            return;
        }
        
        if (now > m) {
            return;
        }
        
        for (int i = begin; i <= n; i++) {
            now += i;
            stack.push(i);
            dfs(stack, i + 1, m, n);
            stack.pop();
            now -= i;
        }
    }

    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        
        while (scanner.hasNextInt()) {
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            Stack<Integer>stack=new Stack<>();
            now=0;
            dfs(stack,1,m,n);
        }
    }
}

发表于 2023-05-15 10:20:49 回复(0)

Java

牛客527227594号

import java.util.*;
public class Main {
public static void getSum(ArrayList<Integer> arr,
int pos,int curSum,int n,int dest){
if(curSum>=dest){
if(curSum==dest){
for(int i=0;i<arr.size()-1;i++)
System.out.print(arr.get(i)+" ");
System.out.println(arr.get(arr.size()-1));
}
return;
}
for(int i=pos;i<=n;i++){
arr.add(i);
getSum(arr,i+1,curSum+i,n,dest);
arr.remove(arr.size()-1);
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
int n=sc.nextInt();
int m=sc.nextInt();
ArrayList<Integer> arr=new ArrayList<>();
int curSum=0;
getSum(arr,1,curSum,n,m);
}
}
}

发表于 2022-09-19 14:01:35 回复(0)

C/C++

牛客243542796号

#include<iostream>
#include<vector>
using namespace std;

int target;
int numa;
int now;

void dfs(vector<int>& temp,int begin)
{
    if(now==target)
    {
        for(int num:temp)
        {
            cout<<num<<' ';
        }
        cout<<endl;
        return ;
    }
    if(now>target)
    {
        return;
    }
    for(int i=begin;i<=numa;i++)
    {
        now+=i;
        temp.push_back(i);
        dfs(temp,i+1);
        temp.pop_back();
        now-=i;
    }
}

int main()
{
    cin>>numa>>target;
    vector<int> ss;
    now=0;
    dfs(ss,1);
}

dfs+回溯的简单应用题

发表于 2022-08-15 18:48:37 回复(0)