求和

#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);
	}
}

代码写的屎一样

#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
*/

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)
 }

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]))

	#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



	**/

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

#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;
}

#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;
    }
}

// 深度优先遍历
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);
            }
        }
    }
}

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;
    }
});

#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;
}

/*思路：实质就是暴力解决问题，将所有的情况枚举出来，然后删选出符合自己要求的结果

   对于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);
    }
}

#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);//一种情况开始 
 }

#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;
}

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;
            }
        }
    }
}

使用回溯法
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();
	}

}