本文共 4714 字，大约阅读时间需要 15 分钟。

原文地址：

分区问题是将已知的集合分成两个子集，这两个子集的元素分别加和是相等的。

例子：

arr[] = {1, 5, 11, 5}Output: true 这个数组可以被分为：{1, 5, 5}和{11}arr[] = {1, 5, 3}Output: false 这个数组不能被分成两个和相同的子集.

根据下面的两个步骤来解决这个问题：

1、计算数组的所有元素的和，如果和是奇数，那么就不能分成两个和相等的子集，返回false。

第一步比较简单，第二步才是关键，第二步可以用递归或者动态规划来解决。

递归方法：

设这个函数为isSubsetSum(arr, n, sum/2)，如果arr[0..n-1]有一个子集的和等于sum/2。isSubsetSum问题可以分成两个子问题：a）isSubsetSum()不考虑最后一个元素（减少n到n-1）；b）isSubsetSum 考虑最后一个元素（sum/2减去arr[n-1]，减少n到n-1）如果以上两条任何一个子问题返回true，那么整个方法返回true。isSubsetSum (arr, n, sum/2) = isSubsetSum (arr, n-1, sum/2) || isSubsetSum (arr, n-1, sum/2 - arr[n-1])

// A recursive Java solution for partition problemimport java.io.*;class Partition{    // A utility function that returns true if there is a    // subset of arr[] with sun equal to given sum    static boolean isSubsetSum (int arr[], int n, int sum)    {        // Base Cases        if (sum == 0)            return true;        if (n == 0 && sum != 0)            return false;        // If last element is greater than sum, then ignore it        if (arr[n-1] > sum)            return isSubsetSum (arr, n-1, sum);        /* else, check if sum can be obtained by any of           the following        (a) including the last element        (b) excluding the last element        */        return isSubsetSum (arr, n-1, sum) ||               isSubsetSum (arr, n-1, sum-arr[n-1]);    }    // Returns true if arr[] can be partitioned in two    // subsets of equal sum, otherwise false    static boolean findPartition (int arr[], int n)    {        // Calculate sum of the elements in array        int sum = 0;        for (int i = 0; i < n; i++)            sum += arr[i];        // If sum is odd, there cannot be two subsets        // with equal sum        if (sum%2 != 0)            return false;        // Find if there is subset with sum equal to half        // of total sum        return isSubsetSum (arr, n, sum/2);    }    /*Driver function to check for above function*/    public static void main (String[] args)    {        int arr[] = {
  3, 1, 5, 9, 12};        int n = arr.length;        if (findPartition(arr, n) == true)            System.out.println("Can be divided into two "+                                "subsets of equal sum");        else            System.out.println("Can not be divided into " +                                "two subsets of equal sum");    }}/* This code is contributed by Devesh Agrawal */

输出：

Can be divided into two subsets of equal sum

最坏情况下的时间复杂度是：O(2^n) ，这种解决方法对于每一个元素都尝试了两种可能（是否包含）。

动态规划方法

当数组中元素的和太大的时候，这个问题就可以用动态规划的方法来解决了。我们可以建立一个大小为(sum/2)*(n+1)的二维数组part[][]。我们可以用自底向上的方法构建这个方法，这样的话每一个entry都有符合下面的式子：

part[i][j] = true if a subset of {arr[0], arr[1], ..arr[j-1]} has sum equal to i, otherwise false

// A dynamic programming based Java program for partition problemimport java.io.*;class Partition {    // Returns true if arr[] can be partitioned in two subsets of    // equal sum, otherwise false    static boolean findPartition (int arr[], int n)    {        int sum = 0;        int i, j;        // Caculcate sun of all elements        for (i = 0; i < n; i++)            sum += arr[i];        if (sum%2 != 0)            return false;        boolean part[][]=new boolean[sum/2+1][n+1];        // initialize top row as true        for (i = 0; i <= n; i++)            part[0][i] = true;        // initialize leftmost column, except part[0][0], as 0        for (i = 1; i <= sum/2; i++)            part[i][0] = false;        // Fill the partition table in botton up manner        for (i = 1; i <= sum/2; i++)        {            for (j = 1; j <= n; j++)            {                part[i][j] = part[i][j-1];                if (i >= arr[j-1])                    part[i][j] = part[i][j] ||                                 part[i - arr[j-1]][j-1];            }        }        /* // uncomment this part to print table        for (i = 0; i <= sum/2; i++)        {            for (j = 0; j <= n; j++)                printf ("%4d", part[i][j]);            printf("\n");        } */        return part[sum/2][n];    }    /*Driver function to check for above function*/    public static void main (String[] args)    {        int arr[] = {
  3, 1, 1, 2, 2,1};        int n = arr.length;        if (findPartition(arr, n) == true)            System.out.println("Can be divided into two "                               "subsets of equal sum");        else            System.out.println("Can not be divided into"                            " two subsets of equal sum");    }}/* This code is contributed by Devesh Agrawal */

输出：

Can be divided into two subsets of equal sum

下图显示了值所在的分区表，这个图来自

时间复杂度是：O(sum*n)

注意：如果数组的元素的和太大的话，这个方法就不再适用了。

参考文献：