求和

import java.util.*;
public class Main{
    public static void dfs(int i, int n, int m, ArrayList<Integer> list){
        if(m == 0){
            for(int j = 0; j < list.size(); j++){
                if(j != list.size()-1){
                    System.out.print(list.get(j) + " ");
                }
                else{
                    System.out.println(list.get(j));
                }
            }
        }
        else{
            for(int j = i+1; j <= n; j++){
                list.add(j);
                dfs(j, n, m-j, list);
                list.remove(list.size()-1);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 1; i <= n; i++){
            list.add(i);
            dfs(i, n, m-i, list);
            list.remove(list.size()-1);
        }
    }
}

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

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

import java.util.Collection;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;
/**
 分析：     
 1、一个数时表示：
 只有 n>m 时 才会有 n内的一个数等于m，可以最后判断考虑
 2、两个数时：
  m=1+(m-1)=2+(m-2)=i+(m-i)控制(i<m-i),如果(m-i<n)那么这一组数字满足要求，添加进入list，
 3、三个数时：
  三个数就是把两个数中较大的数拆分，要增加数字数量，不会出现 m = n 的情况 ，而为了避免重复，较小的数也必须从i+1开始
  那么就是  (i+1)--(m-i-1)范围内查找，用i+1替代i 用m-i-1替代m 循环控制(i< m-i)寻找满足要求的数。  
   ......
  解题：
   1、递归查找
   2、解决一个数问题
   3、排序
   4、输出
 */
public class Main {
static public LinkedList res = new LinkedList(); 
static public void f(    int p/*记录小数字避免重复*/,
                         int n,
                         int m,
                         String rstr/*已经选出的小数字*/) {
    // 每次从 p等于上层的i+1开始循环
    for (int i = p; i <m-i; i++) {
        if (m-i<=n/*两个数中较大的数小于n说明都在范围内*/) {
            //符合范围 保存： 上一层较小的数+拆分后的小数+拆分后的大数
            String s=(rstr+" "+i+" "+(m-i)).trim();
            res.add(s);
        }
        /*  递归  */
        f(i+1, n,m-i/* m */, rstr+" "+i/*将小数保存，拆分大数*/);
    }
}
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    // 递归查找
    f(1, n, m,"");
    // 处理 m=n
    if (m<=n) res.add(m+""); // 最后处理 m==n 时的一
    res.sort(null);            // 排序
    for (String string : res) {
        System.out.println(string);
    }
}
}

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

}

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

//大概思想使用回溯法，左子树进行进栈操作，右子树进行出栈操作，采用深度遍历的方法进行遍历，主要的模板是
1.所有的条件判断，如果是则触发return；
2.否则进行左子树入栈操作，右子树出栈操作
import java.util.ArrayList; import java.util.List; import java.util.Scanner; /**  * Created by Yuan on 2017/3/1.  */ public class Main { private static List<Integer> result=new ArrayList<Integer>(); public static void main(String[] args){
        Scanner scanner=new Scanner(System.in); int n= scanner.nextInt(); int m=scanner.nextInt(); int minMN=m>n?n:m; //get max length of the data  int currentPos=0; int currentSum=0; int[] number=new int[minMN]; for (int i=0;i<minMN;i++){
            number[i]=i+1;
        } DFS(currentPos, minMN, m, currentSum,number);

    } public static void DFS(int currentPos,int n,int m,int currentSum,int[] number){ //判断当前指针是否到达最大数，若到达则结束算法，否则继续    if (currentSum>m){ return;
        } if (currentSum==m){ //print  int len=result.size(); for (int i=0;i<len-1;i++){
                System.out.print(result.get(i)+" ");
            }
            System.out.println(result.get(len - 1)); return;
        } if (currentPos>=n){ return;
        } //左子树进站,进站后需要计算当前的和   currentSum=number[currentPos]+currentSum; result.add(number[currentPos]); DFS(currentPos+1,n,m,currentSum,number); //右边子树出站，出站，只为了促进左子树的查找，右子树的和不会成为这个情况的  //出站  result.remove(result.size()-1); DFS(currentPos + 1, n, m, currentSum-number[currentPos],number);


    }
}