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 List<Integer> list = new ArrayList<>(); public static void main(String[] args){ Scanner in = new Scanner(System.in); int n,m; while(in.hasNext()){ n = in.nextInt(); m = in.nextInt(); Combination(1,n,m,list); //从数字1开始,最大到n,累加和为m } } private static void Combination(int begin,int n,int m,List<Integer> list){ if(m == 0){ for(int j = 0;j<list.size()-1;j++) System.out.print(list.get(j)+" "); System.out.println(list.get(list.size()-1)); return; } if(begin > n || m < 0){ return; } list.add(begin); Combination(begin+1,n,m-begin,list); list.remove(list.size()-1); Combination(begin+1,n,m,list); } }
使用回溯法 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); } }