求解一个集合中是否能组成某个数-子集问题算法和数据结构

【求解一个集合中是否能组成某个数-子集问题】
求解一个集合中是否能组成某个数-子集问题

public class SubSet { public static void main(String[] args) { // 求数组中能否组成9 子集问题以下数中能否组成9 -只考虑正数集合 // 负数动态规划难以创建记录对应关系正数下限为0 负数无下限 int arr1[] = { 3, 34, 4, 12, 5, 2 }; System.out.println("递归求解：" + recSubSet(arr1, 5, 9)); System.out.println("动态规划求解：" + dpSubSet(arr1, 9)); } // 递归实现子集问题 public static boolean recSubSet(int[] arr, int i, int s) {// 剩余要拼的数归零说明已经拼完了递归出口 if (s == 0) { return true; }// 拼到最后一位发现这个数正好是剩下需要的数递归出口 if (i == 0) { return arr[i] == s; }// 此运算值计算正整数值 // 若当前数值大于剩余所要凑的数值规定为不能选因为会出现负数 if (arr[i] > s) { return recSubSet(arr, i - 1, s); }// 两种情况选或不选 // 选 boolean a = recSubSet(arr, i - 1, s - arr[i]); // 不选 boolean b = recSubSet(arr, i - 1, s); // a b 两种任一种成立则成立return a || b; } // 动态规划子集问题 public static boolean dpSubSet(int[] arr, int s) { boolean[][] opt = new boolean[arr.length][s + 1]; for (int i = 0; i < opt.length; i++) { for (int j = 0; j <= s; j++) { if (i == 0) { opt[i][j] = false; if (arr[i] == j) { opt[i][j] = true; } continue; }if (j == 0) { opt[i][j] = true; continue; }if (arr[i] > j) { opt[i][j] = opt[i - 1][j]; //不选 continue; }// 选 boolean a = opt[i - 1][j - arr[i]]; // 不选 boolean b = opt[i - 1][j]; opt[i][j] = a || b; } }System.out.println(); // 计数表 System.out.println("=======动态规划记录表注：【X false】【O true】========"); for (int i = 0; i < opt[0].length; i++) { System.out.print(i + ""); }System.out.println("===>arr[i] 每一个集合项的值，可扩展，无限添加集合项"); System.out.println("----------------------------------------------"); for (int i = 0; i < opt.length; i++) { for (int j = 0; j < opt[i].length; j++) { System.out.print(opt[i][j] ? "O" : "X"); System.out.print(""); }System.out.print("===>"); System.out.print(arr[i]); System.out.println(); }// 取数组最大区间和所定义最大值s位置所存储的值有没有来决定是否能拼装出结果 return opt[arr.length - 1][s]; } }

附执行结果如下：

递归求解：true=======动态规划记录表注：【X false】【O true】======== 0123456789===>arr[i] 每一个集合项的值，可扩展，无限添加集合项 ---------------------------------------------- XXXOXXXXXX===>3 OXXOXXXXXX===>34 OXXOOXXOXX===>4 OXXOOXXOXX===>12 OXXOOOXOOO===>5 OXOOOOOOOO===>2 动态规划求解：true