[编程题]求和
#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
回复(29)
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)
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()
}
}
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);
}
}
}
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)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
/**
* Created by hongjing on 2017/9/10.
*/
public class Main {
public static List sum(int n, int m){
List<Integer> result = new ArrayList<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 1; i <= n; i++){
map.put(i, i);
}
for (int i = 1; i < m / 2 + 1; i++){
if (map.containsKey(m - i)){
result.add(i);
result.add(m - i);
}
}
if (n == m){
result.add(m);
}
return result;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String line = in.nextLine();
String ta = null;
if (in.hasNext()){
ta = in.nextLine();
}
List<Integer> result = sum(Integer.parseInt(line), Integer.parseInt(ta));
int sum = result.size();
for (int i = 0; i < sum;){
//奇数个结果
if (i == sum - 1 && sum % 2 != 0){
System.out.println(result.get(i));
i ++;
}else {
System.out.println(result.get(i) + " "+ result.get(i + 1));
i += 2;
}
}
}
}
编辑于 2017-09-10 11:23:33
回复(0)
使用回溯法
import java.util.*;
public class Main {
static ArrayList<List<Integer>> res = new ArrayList<>();
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int N = cin.nextInt();
int M = cin.nextInt();
List<Integer> list = new ArrayList<>();
//当n>m时，其实大于部分是不可能取到的
int min = N < M ? N : M;
printList(min, M, 0, 1, list);
//按照字典序排列
Collections.reverse(res);
for (int i = 0; i < res.size(); i++)
print(res.get(i));
}
private static void printList(int N, int M, int m, int n, List<Integer> list) {
if (m == M) {
ArrayList<Integer> result = new ArrayList<Integer>();
result.addAll(list);
res.add(result);
return;
}
if (n > N || m > M) {
return;
}
//不放入
printList(N, M, m, n + 1, list);
//放入
list.add(Integer.valueOf(n));
printList(N, M, m + n, n + 1, list);
//回溯
list.remove(Integer.valueOf(n));
}
private static void print(List<Integer> list) {
for (int i = 0; i < list.size(); i++) {
if (i != 0)
System.out.print(" ");
System.out.print(list.get(i));
}
System.out.println();
}
}
发表于 2017-09-07 14:29:05
回复(0)
问题信息
难度：
121条回答
368收藏
26705浏览
通过挑战的用户
查看代码-
2023-01-23 17:50:55
-
2022-12-28 18:10:34
-
2022-12-16 19:55:47
-
2022-12-14 16:46:56 -
2022-12-12 13:15:11
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
