首页 > 试题广场 > 求和
[编程题]求和
  • 热度指数:20014 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
输入两个整数 n 和 m,从数列1,2,3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来

输入描述:
每个测试输入包含2个整数,n和m


输出描述:
按每个组合的字典序排列输出,每行输出一种组合
示例1

输入

5 5

输出

1 4<br/>2 3<br/>5
#include<iostream>
#include<vector>
using namespace std;
void help(int n, int m, vector<int>& v, int beg) {
	//if (beg>n) return;
	if (m == 0) {
		for (int i = 0; i<v.size(); i++) {
			i == 0 ? cout << v[i] : cout << " " << v[i];
		}
		cout << endl;
	}
	for (int i = beg; i <= n&&i <= m; i++) {
		v.push_back(i);
		help(n, m - i, v, i + 1);
		v.pop_back();
	}
}
int main() {
	int n, m;
	while (cin >> n >> m) {
		vector<int>v;
		help(n, m, v, 1);
	}
}

发表于 2017-03-19 22:00:12 回复(28)
#include<stdio.h>
#include<vector>
using namespace std;
vector<int> d;
void dfs(int,int);
int N,M;
int main(){
	while(scanf("%d%d",&N,&M)!=EOF)
		dfs(1,0);
}
void dfs(int index,int sum){
	if(sum>M) return;
	if(sum==M){
        int i;
		for(i=0;i<d.size()-1;i++) 
            printf("%d ",d[i]);
        printf("%d\n",d[i]);
	}
	for(int i=index;i<=N;i++){
		d.push_back(i);
		dfs(i+1,sum+i);
		d.pop_back();
	}
}

发表于 2017-09-12 19:04:07 回复(3)
import java.util.ArrayList;
import java.util.Scanner;

public class Main{
	static ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
	static ArrayList<Integer> list = new ArrayList<>();
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n, m;
		
		while(sc.hasNext()) {
			n = sc.nextInt();
			m = sc.nextInt();
			dfs(1, m, n);
			for(ArrayList<Integer> l : res) {
				int i = 0;
				for(; i < l.size() - 1; i++) {
					System.out.print(l.get(i) + " ");
				}
				System.out.println(l.get(i));
			}
		}
	}
	
	public static void dfs(int index, int count, int n) {
		if(count == 0) {
			res.add(new ArrayList<>(list));
		}
		else {
			for(int i = index; i <= count && i <= n; i++) {
				list.add(i);
				dfs(i + 1, count - i, n);
				list.remove(list.size() - 1);
			}
		}
	}
}

编辑于 2017-07-24 10:54:55 回复(8)

代码写的屎一样

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;
//常量区
int n, m, A[200];
vector<string> vec;
//函数区

void solve(int pos, int cnt, int num){
    if(cnt == num){
        int sum = 0;
        for(int i = 1; i <= n; i++) 
            if(A[i] == 1) sum += i;
        if(sum == m){
            string tmp = "";
            for(int i = 1; i <= n; i++){
                if(A[i] == 1) {char c = '0' + i; tmp = tmp + c;}
            }
            vec.push_back(tmp);
        } 
        return;
    }
    if(pos == n + 1) return;
    if(!A[pos]){
        A[pos] = 1;
        solve(pos + 1, cnt + 1, num);
        A[pos] = 0;
    }
    solve(pos + 1, cnt, num);
}

int cmp(string a,string b){
    return a.compare(b)<0;
}

void show(){
    int size = vec.size();
    sort(vec.begin(), vec.end(), cmp);
    for(int i = 0; i < size; i++){
        for(int j = 0; j < vec[i].length(); j++){
            if(j == 0) {printf("%d", vec[i][j] - '0');}
            else printf(" %d", vec[i][j] - '0');
        }
        printf("\n");
    }
}

//main函数
int main(){
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        memset(A, 0, sizeof(A));
        solve(1, 0, i);
    }
    show();
       return 0;
}
/* 
5 5
*/
编辑于 2018-09-18 14:28:37 回复(1)
var readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})

rl.on('line', function(line) {
    var tokens = line.split(' ')
    var sumsArr = []
    findSumArr(parseInt(tokens[0]), parseInt(tokens[1]), [], sumsArr)
    sumsArr.sort().forEach(function(item) {
      console.log(item);
    })
})

 function findSumArr(n, m, sumArr, sumsArr) {
   if(m < 1) {//m===0
     sumsArr.push(sumArr.sort().join(' '))
     return
   }
   if(n < 1) {
     return
   }
   // 如果n大于m,则将n赋值为m(大于m的值无用
   if(n > m) {
     n = m
   }

   // 注意:这里不能直接使用 tmpArr=sumArr
   var tmpArr = []
   sumArr.forEach(function(item) {
     tmpArr.push(item)
   })
   // 1. 不将n放入数组
   findSumArr(n-1, m, sumArr, sumsArr)
   // 2. 将n放入数组
   tmpArr.push(n)
   findSumArr(n-1, m-n, tmpArr, sumsArr)
 }
编辑于 2017-03-14 12:28:59 回复(3)
 n, m = list(map(int, input().split(' ')))
li = []

def f(n, m, l, k):
    if m == 0:
        print(' '.join(l))
    for i in range(k, n+1):
        if i > m:
            break
        l.append(str(i))
        f(n, m-i, l, i+1)
        l.pop()
        
f(n, m, li, 1)
思路DFS
发表于 2017-10-12 10:59:03 回复(2)
def rec(i, m, res):
    ans = []
    for j in range(i, n+1):
        if j == m:
            ans.extend([x+[j] for x in res])
            break
        if j < m:
            ans.extend(rec(j+1, m-j, [x+[j] for x in res]))
        else:
            continue
    return ans


if __name__ == '__main__':
    n, m = [int(x) for x in input().split()]
    ans = rec(1, m, [[]])
    for a in ans:
        print(' '.join([str(x) for x in a]))
编辑于 2017-10-01 20:21:36 回复(4)










#include <iostream>

#include <algorithm>

using namespace std;

void slove(int now, int pre) {

    cout << pre << " ";

    if(now - (pre + 1) > (pre + 1)) {

        for(int i = 1; now - (pre + i) > (pre + i); i++) {

            if(i != 1) cout << pre << " ";

            slove(now - (pre + i), pre + i);

        }

    } else {

        cout << now << endl;

    }

}

int main()

{

    int n, m;

    cin >> n >> m;

    int e = min(n, m / 2);

    for(int i = 1; i <= e; i++) {

        if(m - i <= i) continue;

        slove(m - i, i);

    }

    if(n >= m) cout << m << endl;

    return 0;

}

/**

 5 5

 3 7

**/


发表于 2017-09-12 12:10:14 回复(0)

其实就是回溯算法,把所有的状态都列出来,利用简单的剪枝方法,提高效率。具体代码里都有注释

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

vector<int> v;
void find_ans(vector<int> ret, int cur_pos, int n, int cur_sum, int sum) {
    if (cur_pos >= n) return ;
    cur_sum += v[cur_pos];
    ret.push_back(v[cur_pos]);
    if (cur_sum == sum) {
        for (int i = 0; i < ret.size() - 1; ++i) {
            cout << ret[i] << " ";
        }
        cout << ret[ret.size() - 1];
        cout << endl;
        return ;
    } else if (cur_sum > sum) { // 大于sum,就没必要再继续往下了,剪枝操作
        return ;
    }
    // 把当前的下标位置的值放进去,继续下一个位置
    find_ans(ret, cur_pos+1, n, cur_sum, sum);
    // 不要当前值,从下一个位置搜索,意思大概就是不从1开始找了,从2开始找
    vector<int>::iterator it = ret.end();
    --it;
    ret.erase(it);
    find_ans(ret, cur_pos+1, n, cur_sum - v[cur_pos], sum);
    // 总体思想就是当前位置的数是要还是不要的事情,列出来所有的可能,挨个输出就行了
}
int main() {
    int n, num;
    cin >> n >> num;

    for (int i = 0; i < n; ++i) {
        v.push_back(i+1);
    }
    // 因为如果n大于num的话,那么num后面的数字肯定不需要再考虑了,所以我们只需要考虑从1~num之间的可能组合就行了
    if (n >= num) n = num;

    vector<int> ret;
    int sum = 0;
    // 利用递归的方法来做,0是当前位置,n是最大下标,sum是当前和,num就是要求的结果
    find_ans(ret,0,n,sum,num);
    return 0;
}
发表于 2017-02-16 21:16:57 回复(1)
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    int m = 0;
    int n = 0;
    cin >> n >> m;
    int bit = 1 << n;
    int count = 0;
    int current = 0;
    vector<string> vec;
    while (current++ < bit)
    {
        int sum = 0;
        string s;
        for (int i = 0; i < n; i++)
        {
            if ((current >> i) & 1)
            {
                sum = sum + i + 1;
                s = s + to_string(i+1);
            }
        }
        if (sum == m)
        {
            count++;
            vec.push_back(s);
        }
    }
    sort(vec.begin(), vec.end());
    for (int i = 0; i < vec.size(); i++)
    {
        for (int j = 0; j < vec[i].size() - 1; j++)
        {
            cout << vec[i][j] << ' ';
        }
        cout << vec[i][vec[i].size() - 1] << endl;
    }
}

发表于 2017-12-17 14:17:26 回复(1)
// 深度优先遍历
import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            ArrayList aList = new ArrayList<Integer>();
            for(int i=1;i<=n;i++){
                aList.add(i);
                count(m, i, i,n,aList);
                aList.remove(aList.size()-1);
            }
        }
    }
    public static void count(int m, int sum, int currentVal, int n, ArrayList aList){
        if(sum>m)return;
        if(sum==m){
            StringBuilder sb = new StringBuilder();
            Iterator it = aList.iterator();
            while(it.hasNext()){
                sb.append(it.next() + " ");
            }
            System.out.println(sb.toString().trim());
        }else{
            for(int i=currentVal+1;i<=n;i++){
                aList.add(i);
                count(m, sum+i, i, n,aList);
                aList.remove(aList.size()-1);
            }
        }
    }
}

发表于 2017-09-05 22:30:18 回复(0)
process.stdin.resume();
process.stdin.setEncoding('ascii');
var input='';
process.stdin.on('data', function(data){
        input+=data;
        var inputArr=input.split(" "),
            n=inputArr[0],
            m=inputArr[1],
            result=[];
        var allComb=getAllComb(n);  //求出1至n所有的组合
        allComb.forEach(function(ele){  //筛选出所有和为m的组合
            if(ele.reduce(function(a,b){returna+b})==m){
                result.push(ele.join(" "))
            }
        });
        var res=[];
        for(var i=0;i<result.length;i++){    //调整至满足要求的顺序
            res[i]=result[result.length-i-1];
        }
        console.log(res.join("\n"));    //换行输出所有结果

    function getAllComb(n){ //用二进制数表示所有可能的组合,再用下标的方法求出所有组合
        var max=Math.pow(2,n),
            arr=[],
            res=[];
        for(var i=1;i<=n;i++){
            arr.push(i);
        }
        for(var i=1;i<max;i++){
            var temp=i.toString(2),
                size=temp.length,
                subRes=[];
            if(size<n){for(var j=0;j<n-size;j++){temp="0"+temp}}  //补足二进制数temp前的空位
            for(var k=0;k<arr.length;k++){
                if(temp[k]==true){
                    subRes.push(arr[k])
                }
            }
            res.push(subRes);
        }
        return res;
    }
});
编辑于 2017-03-14 15:47:30 回复(1)
public class ListAllNum {
public static void printList(int m,int n,List<Integer>list){
if(m == 0){
System.out.println(list); 
return;
}
if(n<=0 || m<0){
return;
}
List list1 = new ArrayList<>(list);
printList(m, n-1, list);
list1.add(n);
printList(m-n, n-1, list1);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m  = in.nextInt();
List<Integer> list = new ArrayList<>();
int up = n > m ? m : n;
printList(m,up,list);
}
}
发表于 2017-02-14 13:53:15 回复(2)
const readline = require('readline')

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
})
let n = 0
let m = 0
rl.on('line', str=>{
    str.split(' ').forEach((item, i)=>{
        if(i===0){
            n = parseInt(item)
        }else if(i===1){
            m = parseInt(item)
        }
    })
    help(n, m, [], 1)
    if(n>=m){
        console.log(m)
    }
})
function help(n, m, addArr, start){
    let midNum = m/2
    if(midNum>=n || midNum<1)
        return 
    for(let i=start; i<midNum; i++){
        if(m-i<=n){
            //打印
            console.log([...addArr, i, m-i].join(' '))
        }
        //递归
        addArr.push(i)
        help(n, m-i, addArr, i+1)
        addArr.pop()
    }
}
发表于 2021-04-11 09:38:18 回复(0)
#include <iostream>
#include <vector>
using namespace std;
void dfs(int n, int m, vector<int>& v, int beg){
    // m == 0 为递归结束条件. 此时 v 中可能已经包含了若干个元素了
    //并且 v 中的内容就是一组结果.
    if(m == 0){
        for(int i = 0; i < v.size(); ++i){
            i == 0 ? cout << v[i] : cout << " " << v[i];
        }
        cout << endl;
    }
    for(int i = beg; i <= n && i <= m; ++i){
        // 以下几行代码是该题目的关键. 问题的转换.
        // 为了求 i -> n 有多少种情况和为 m, 则把问题转换为
        // i + 1 -> n 有多少中情况和为 m - i
        v.push_back(i);
        dfs(n, m - i, v, i + 1);
        v.pop_back();
    }
}
int main(){
    int n,m;
    while(cin >> n >> m){
        vector<int> v;
        dfs(n,m,v,1);
    }
    return 0;
}

发表于 2020-09-04 20:55:06 回复(0)
唉,不会dfs啊,只会用暴力的for循环去搞
import itertools

n, m = list(map(int, input().split(' ')))
list1 = []
list2 = []

for i in range(1, n + 1):
    if i == m:
        list1.append(i)
        continue
    else:
        list2.append(i)

list3 = []
for i in range(1, len(list2) + 1):
    iter = itertools.combinations(list2, i)
    list3.append(list(iter))

list4 = []
for i in list3:
    for j in i:
        if sum(j) == m:
            list4.append(j)
list4.sort()
for i in list4:
    for j, k in enumerate(i):
        if j == len(i) - 1:
            print(k)
        else:
            print(k, end=" ")
if not list1:
    pass
else:
    print(list1[0])


发表于 2020-03-29 21:09:44 回复(0)
/*思路:实质就是暴力解决问题,将所有的情况枚举出来,然后删选出符合自己要求的结果

   对于1,2,3....n的数中随便选出其中几个出来,只要和是m,就以字典序输出
   其实就是取决于我对于每个数的取舍问题:
     比如  对于数字 1 我只有两种策略:要或者不要   
                                        要的我用res记录下来,并且加到sum中
                                        不要的我直接过(可参照下面代码)
           对于数字 2 我也只有两种策略:要或者不要  
   依次类推..........

   最后的结束标志:就是我到最后一个数字 n 判定完成之后,看我的 sum 和 m 是否相等
                   相等就输出,然后结束这一个分支的递归
                   不相等就不输出,但是也要结束这个分支的递归   

   按照先要再不要的策略,最后输出的结果就是字典序。
*/

import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        String res = "";//用来记录被选到的数
        int sum = 0; //用来记录被选到数加起来的总和
        int []num = new int[n];
        int j =1;
        for(int i = 0;i < n;i++)
              num[i] = j++; 
        process(num,m,res,sum,0);
    }
    
    public static void process(int[] num,int m,String res,int sum,int i){
        if(i == num.length){
            if(sum == m)
                               //这里用trim()方法就是去除每个输出最后的一个空格
                System.out.println(res.trim());
            return;
        }
               //表示我将num[i]这个数选到了
        process(num,m,res+num[i]+" ",sum+num[i],i+1);
                
               //表示我不要num[i]这个数
        process(num,m,res,sum,i+1);
    }
}

发表于 2019-03-04 16:52:29 回复(0)

#include<stdio.h>
int n,c[10],k,i,m;
 void print(int i,int m,int k)
 {
     c[k]=i;
     if(i==m&&m<=n)
     {
         for(int j=1;j<k;j++)
         printf("%d ",c[j]);
         printf("%d\n",c[k]);//一种情况结束 
     }
     else
     {
         for(int j=i+1;j<=m-i;j++)//核心递归,使得左边数小于右边,并且能通过递归嵌套,找出子集数量2以上的和为M的情况
         print(j,m-i,k+1);
     }
 }
 int main ()
 {
     scanf("%d %d",&n,&m);
     for(i=1;i<=n;i++)
         print(i,m,1);//一种情况开始 
 }

发表于 2018-09-22 19:54:40 回复(0)
从1到n,每个数都有可能选或者不选,ArrayList<Integer> list 记录已经选的数,用于打印输出,m是题目要的和,sum是当前累加的和,now就是已经从1走到几了,max是n,或者m,就是说now大于这个数后sum就不必再加now了,比max大的数肯定已经比m大了,若sum>m或者now>max+1;说明上一步list.add(now);是没用的,需要去掉 list.remove(new Integer(now));代码如下

import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int n = in.nextInt();
            int m = in.nextInt();
            getCount(1,n<m?n:m,m,0,new ArrayList<Integer>(),false);
        }
    }
    public static void getCount(int now,int max,int m, int sum,ArrayList<Integer> list,boolean isadd){
        if(now > max+1 || sum>m){
            if(isadd)
                list.remove(new Integer(now-1));
            return;
        }
        else if(m==sum){
            for(int i=0;i<list.size()-1;i++)
                System.out.print(list.get(i)+" ");
            System.out.println(list.get(list.size()-1));
        }
        else{
            list.add(now);
            getCount(now+1,max,m,sum+now,list,true);
            list.remove(new Integer(now));
            getCount(now+1,max,m,sum,list,false);
        }
    }
}

编辑于 2018-08-28 22:45:27 回复(0)
#include <iostream>
#include <vector>
using namespace std;

void Solve(int n, int m, vector<int> &v, int cnt)
{     if(m==0)     {         for(int i=0;i<v.size();i++)         {             if(i==v.size()-1)                 cout<<v[i]<<endl;             else                 cout<<v[i]<<" ";         }     }     for(int i=cnt;i<=m && i<=n;i++)     {         v.push_back(i);         Solve(n,m-i,v,i+1);         v.pop_back();     }
}

int main()
{     int n,m;     while(cin>>n>>m)     {         vector<int> v;         Solve(n,m,v,1);     }     return 0;
}

发表于 2018-01-22 00:46:28 回复(0)