java实现子集和问题

1 问题描述

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

2 解决方案

2.1 全排列思想求解

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

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

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

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

package com.liuzhen.chapter12;

import java.util.ArrayList;

public class SubSet {

    public ArrayList<Integer> list = new ArrayList<Integer>();   //用于存放求取子集中的元素

    //求取数组链表中元素和

    public int getSum(ArrayList<Integer> 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);

    }

}

运行结果：

巴特西

java实现子集和问题

最新文章

热门文章