1 问题描述

求n个正整数构成的一个给定集合A = {a1,a2,a3,...,an}的子集，子集的和要等于一个给定的正整数d。请输出所有符合条件的子集。

2 解决方案

本文下面编码思想参考自文末，下面的思想讲解直接引用文末参考资料1。

2.1 全排列思想求解

方法1：首先，将子集保存在一个数组链表中，每次往链表中添加一个元素；

从空集增加到最大集，再回溯，递归返回的时候，再将链表最后一个元素从子集移出；

这样就实现了，元素在与不在子集中，这两种状态。

注意，每次加入一个元素得到的，子集数组中的元素就构成了一个子集。

具体代码如下：

package com.liuzhen.chapter12;import java.util.ArrayList;public class SubSet {        public ArrayList
    
      list = new ArrayList
     
      ();   //用于存放求取子集中的元素    //求取数组链表中元素和    public int getSum(ArrayList
      
        list) {        int sum = 0;        for(int i = 0;i < list.size();i++)            sum += list.get(i);        return sum;    }    /*     * 参数step：选中数组A中第step个元素为子集元素     * 函数功能：求取数组A中一个子集元素，其相加之和等于m     */    public void getSubSet(int[] A, int m, int step) {        while(step < A.length) {            list.add(A[step]);   //递归执行语句，向数组链表中添加一个元素            if(getSum(list) == m)   //链表中元素和等于m                 System.out.println(list);            step++;            getSubSet(A, m, step);            list.remove(list.size() - 1);   //回溯执行语句，删除数组链表最后一个元素        }    }        public static void main(String[] args) {        SubSet test = new SubSet();        int[] A = new int[6];        for(int i = 0;i < 6;i++) {            A[i] = i + 1;        }        test.getSubSet(A, 8, 0);    }}

运行结果：

[1, 2, 5][1, 3, 4][2, 6][3, 5]

2.2 状态空间树思想求解

方法2：从元素在与不在子集这两种状态来考虑，因为每个元素都有两种状态，

可以理解为一种二叉树的形式，如下图：

每一个元素带有一个属性，在不在子集中，1(true)表示在子集，0(false)表示不再自己中。

每个元素的状态初始化为1，实际上无需去构造二叉树。

第一个递归将所有元素逐个放入子集，当所有元素放入子集后回溯。

第一次递归返回后，将最后一个元素移出子集，这样每个元素在与不在子集的状态都可以遍历到，每次遍历到最后一个元素时，按照元素的状态打印字符序列，得到的就是一个子集。

具体代码如下：

package com.liuzhen.chapter12;import java.util.ArrayList;public class SubSet {        public int getSum1(boolean[] visited, int[] A) {        int sum = 0;        for(int i = 0;i < A.length;i++) {            if(visited[i])                sum += A[i];        }        return sum;    }        public void getSubSet1(boolean[] visited, int[] A, int m, int step) {        if(step == A.length) {            if(getSum1(visited, A) == m) {                for(int i = 0;i < A.length;i++) {                    if(visited[i])                        System.out.print(A[i]+" ");                }                System.out.println();            }            return;        }        visited[step] = true;        getSubSet1(visited, A, m, step + 1);        visited[step] = false;        getSubSet1(visited, A, m, step + 1);    }        public static void main(String[] args) {        SubSet test = new SubSet();        int[] A = new int[6];        boolean[] visited = new boolean[6];        for(int i = 0;i < 6;i++) {            A[i] = i + 1;            visited[i] = false;        }        test.getSubSet1(visited, A, 8, 0);    }}

运行结果：

1 2 5 1 3 4 2 6 3 5

参考资料：

上一篇：算法笔记_075:蓝桥杯练习最短路（Java）

下一篇：算法笔记_073:哈密顿回路问题（Java）

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！