解题思路:使用深搜方法,其实我们每次都是在考虑当前的数要或者不要两种情况,那么就是每次深搜下探延伸出两条支线。
参考代码:
//经典部分和问题的变体 public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); n = in.nextInt(); int[] arr = new int[n]; for(int i = 0; i < n; i++) { arr[i] = in.nextInt(); } K = in.nextInt(); dfs(arr, 0, n - 1); System.out.println(cnt); in.close(); } public static int n; //几个数字 public static int K; //要求的和 public static int cnt = 0; public static ArrayList<Integer> list = new ArrayList<>(); //存放选入的数字 /* * arr 待选数组 * k 目前已有和 * cur 目前决定第几个数字的选取 */ public static void dfs(int[] arr, int k, int cur) { if(cur == -1) { if(list.size() != 0) { if(k == K) { cnt++; for(int i = list.size() - 1; i >= 0; i--) { System.out.print(list.get(i)); if(i != 0) { System.out.print(" "); } } System.out.println(); } } return; } //不选cur dfs(arr, k, cur - 1); //选cur list.add(arr[cur]); dfs(arr, k + arr[cur], cur - 1); list.remove(list.size() - 1); //回溯 } }
0.0分
1 人评分
C二级辅导-同因查找 (C语言代码)浏览:579 |
C语言考试练习题_排列 (C语言代码)浏览:1315 |
C语言程序设计教程(第三版)课后习题11.5 (C语言代码)浏览:889 |
c primer plus 第十二章 12.1小节浏览:377 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:597 |
数组输出 (C语言代码)错误???浏览:562 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:994 |
简单的a+b (C语言代码)浏览:335 |
C语言训练-大、小写问题 (C语言代码)浏览:724 |
printf基础练习2 (C语言代码)浏览:746 |