【子集或者DFS】部分和问题

题目：

　　给定整数序列a₁,a₂,...,a_n,判断是否可以从中选出若干数,使它们的和恰好为k。1≤n≤20 -10⁸≤a_i≤10⁸ -10⁸≤k≤10⁸
　　输入:

n=4

a={1,2,4,7}

k=13

　　输出:

Yes (13 = 2 + 4 + 7)

思路：

　　这里记录一下为什么会想到用子集去做这道题目，这道题目是关于从几个数中找出几个关于符合某种关系的数，呐，根据模式匹配法很容易想到这种方法，而关于这种方法也可以推广开来，也就是说只要在n个数据中找几个数据都可以用求子集的方式去做。

代码：

 import java.util.ArrayList;

 import java.util.Arrays;

 import java.util.Scanner;

 public class 部分和 {

     private static int kk;

     public static void main(String[] args) {

         Scanner sc = new Scanner(System.in);

         int n = sc.nextInt();

         int[] A = new int[n];

         for (int i = 0; i < n; i++) {

           A[i] = sc.nextInt();

         }

         int k = sc.nextInt();//

         System.out.println("================解法一=============");

         ArrayList<ArrayList<Integer>> subsets = getSubsets(A, A.length);

         int count = 0;

         for (int i = 0; i < subsets.size(); i++) {

             for (int j = 0; j < subsets.get(i).size(); j++) {

                 count += subsets.get(i).get(j);

                 if (count==k&&j==subsets.get(i).size()-1) {

                     System.out.println("yes k = "+subsets.get(i));

                 }

             }

             count = 0;  // 如果没找到 要将count置为0

         }

 //        System.out.println(subsets);

         System.out.println("================解法二=============");

         kk = k;

         dfs(A, k, 0, new ArrayList<Integer>());

     }

     /**

      * 本题最优解法  二进制求取所有子集然后求和等于k解决问题

      */

     public static ArrayList<ArrayList<Integer>> getSubsets(int []A,int n){

         Arrays.sort(A);  // 正序排序

         ArrayList<ArrayList<Integer>> res = new ArrayList<>();  //大集合

         for(int i = ex(2, n);i>0;i--){         //大数字-1

             ArrayList<Integer> s = new ArrayList<>();  //对每个i建立一个集合

             for(int j = n-1;j>=0;j--){    //检查哪个位上的二进制为1,从高位开始检查,高位对应着数组靠后的元素

                 if(((i>>j)&1)==1){

                     s.add(A[j]);

                 }

             }

             res.add(s);

         }

         // 生成的结果逆序排序，如果要生成正序排列，很难完成，只有数组反转实现。

         return res;

     }

     public static int ex(int a,int n){

         if(n==0)return 1;

         if(n==1)return a;

         int temp = a; // a的1次方

         int res = 1;

         int exponent = 1;

         while((exponent<<1)<n){

             temp = temp * temp;

             exponent = exponent << 1;

         }

         res *= ex(a,n-exponent);

         return res * temp;

     }

     private static void dfs(int[] a, int k, int cur, ArrayList<Integer> ints) {

         if (k == 0) {

             System.out.print("Yes (" + kk + " = ");

             int size = ints.size();

             for (int i = 0; i < size; i++) {

                 System.out.print(ints.get(i) + (i == size - 1 ? "" : " + "));

             }

             System.out.println(")");

             System.exit(0);

         }

         if (k < 0 || cur == a.length)

             return;

         dfs(a, k, cur + 1, ints);// 不要cur这个元素

         ints.add(a[cur]);

         int index = ints.size() - 1;

         dfs(a, k - a[cur], cur + 1, ints);

         ints.remove(index);// 回溯

     }

 }

结果：

巴特西

【子集或者DFS】部分和问题

最新文章

热门文章