百词斩第二题

我是暴力求解的，两个标志位，左右往中间缩小

import java.util.Arrays;import java.util.Scanner; public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] numbers = new int[n];for (int i=0;i<n;i++){numbers[i] = sc.nextInt();}Arrays.sort(numbers);int k = sc.nextInt();boolean result = sumofK(numbers,n,k);System.out.println(result);} private static boolean sumofK(int[] numbers, int n, int k) { if (n==1) {//计算到第一个元素时 if (numbers[0]==k) { return true; } else{ return false; } } boolean b=sumofK(numbers, n-1, k-numbers[n-1]); if (b) {//这个解中包含a[n-1] return true; } else {//解中不包含a[n-1]，继续计算前面的数组中是否有解 return sumofK(numbers, n-1, k); } } }

dfs 取或者不取

dfs(i+1,sum+num[i]) or dfs(i+1,sum)

//这段代码只有60%通过率不知道为啥 public static boolean dfs(int i, int sum, int[] arr) { if (sum > k) return false; if (i == n) return sum == k; if (dfs(i + 1, sum, arr)) { return true; } if (dfs(i + 1, sum + arr[i], arr)) { return true; } return false; }

import java.util.*; public class P2 {     /*     任意多个数字组合, 和为定值          5     1 2 3 4 5     10          4     3 1 5 9     14     */          private static int target = 0;     private static int[] nums;     private static int N;     private static boolean flag = false;          public static void dfs(int depth, int sum) {         if (sum == target) {             flag = true;             return ;         } //        if (flag == true)    // 可以更快收敛 //            return ;         for (int i = depth; i < N; i++) {             dfs(depth+1, sum + nums[depth]);             dfs(depth+1, sum);         }     }          public static void main(String[] args) {         Scanner input = new Scanner(System.in);                  N = input.nextInt();         nums = new int[N];         for (int i = 0; i < N; i++)             nums[i] = input.nextInt();         target = input.nextInt();                  dfs(0, 0);         System.out.println(flag);                  input.close();     } }

我感觉像是求组合的变形，在求组合的过程中判断这个组合的和是不是指定值

百度就能找到原题