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

    如对于n=5, m = 5, 则由[1,4], [2, 3], [5]满足。

    注意：题目隐含数字不可重复

    直接上代码：

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

    深度搜索的典型应用，这个题目的变种很多，但基本都是用的深搜，用于复习还是很不错的

    程序中基本只有一个地方需要注意下，就是result.add(new ArrayList<>(list))，不能直接写result.add(list), 否则会由于引用的问题导致所有结果出错，result.add(new ArrayList<>(list))这种写法应该是最简单的list的复制方法了。

    ps:

1. 其实代码还可以缩短，print函数可以省去，将打印结果的部分写在dfs函数中的if中。写成这样主要是为了调用方便，也比较直观。

2. 程序中提供的用于求和的数为1~n, 其实可以理解为有序的数组。但如果提供的数不是有序的，则需要对其进行修改。比如如果提供的数是{5,5,10,2,3}，和为15，则原来的程序无法得出{5,5,2,3}这个结果。因为当list中包含两个5的时候，再遇到10时，不会进入for循环，此时result.addAll()运行结束，会直接执行list.remove(list.size()-1), 也就是会移除list中最后一个5，使list变为{5}，再次执行循环时，dfs会从2位置开始执行，也就是列表的第三个数，这样，{5,5,2,3}的组合就永远不会出现。

    所以，对于无序的数组，需要将

for(int i = index; i <= count && i <= n; i++) {    list.add(i);    result.addAll(dfs(i + 1, count - i, n, list));    list.remove(list.size() - 1);}

    改为类似下面的形式。其中arr表示用于求和的数组，sum表示和。

for (int j = index; j < arr.length; j++) {    if (arr[j] <= sum) {         list.add(j);         result.addAll(dfs(arr, j + 1, sum - arr[j], list));    } else {         if (j == arr.length - 1) {            list.remove(list.size() - 1);         }    }}

附上遇到的dfs的题：

    http://acm.nyist.net/JudgeOnline/problem.php?pid=27

    http://blog.csdn.net/qq_32183461/article/details/50705953