Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

Idea 1. Subset sum

[1, 5, 11, 5]

containing 1: [1], sum {1}

containing 5: [5], [1, 5] sum {5, 6}

containing 11: [11], [1, 11], [5, 11], [1, 5, 11] {11, 12, 16, 17}

containing: 5: [5], [1, 5], [5, 5], [1, 5, 5], [11, 5], [1, 11, 5], [5, 11, 5], [1, 5, 11, 5], {5, 6, 10, 11, 16, 17, 21, 22}

Time complexity: O(2^n -1)

Space complexity: O(2^n -1)

 class Solution {

     public boolean canPartition(int[] nums) {

         int totalSum = 0;

         for(int num: nums) {

             totalSum += num;

         }

         if(totalSum%2 != 0) {

             return false;

         }

         List<List<Integer>> endSum = new ArrayList<>();

         for(int i = 0; i < nums.length; ++i) {

             List<Integer> curr = new ArrayList<>();

             if(nums[i] == totalSum/2) {

                 return true;

             }

             curr.add(nums[i]);

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

                 for(int val: endSum.get(j)) {

                     int currSum = val + nums[i];

                     if(currSum == totalSum/2) {

                         return true;

                     }

                     curr.add(currSum);

                 }

             }

             endSum.add(curr);

         }

         return false;

     }

 }

Idea 2: dynamic programming. Let dp[i][j] represents if the subset sum from num[0..i] could reach j,

dp[i][j] = dp[i-1][j] not picking nums[i],

　　　　dp[i-1][j-nums[i]] picking nums[i]

Note. to initialise dp[-1][0] = 0

Time complexity: O(n*target)

Space complexity: O(n*target)

 class Solution {

     private void backtrack(int[] nums, int i, boolean[][] dp, int target) {

         if(i > nums.length) {

             return;

         }

         for(int j = 1; j <= target; ++j) {

             dp[i][j] = dp[i-1][j];

             if(j >= nums[i-1]) {

                 dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];

             }

         }

         backtrack(nums, i+1, dp, target);

     }

     public boolean canPartition(int[] nums) {

         int totalSum = 0;

         for(int num: nums) {

             totalSum += num;

         }

         if(totalSum %2 != 0) {

             return false;

         }

         int n = nums.length;

         int target = totalSum/2;

         boolean[][] dp = new boolean[n+1][target+1];

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

             dp[i][0] = true;

         }

         backtrack(nums, 1, dp, target);

         return dp[n][target];

     }

 }

 class Solution {

     public boolean canPartition(int[] nums) {

        int totalSum = 0;

        for(int num: nums) {

            totalSum += num;

        }

        if(totalSum %2 != 0) {

            return false;

        }

        int target = totalSum/2;

        int m = nums.length;

        boolean[][] dp = new boolean[m+1][target+1];

        dp[0][0] = true;

        for(int i = 1; i <= m; ++i) {

            for(int j = 1; j <= target; ++j) {

                dp[i][j] = dp[i-1][j];

                if(j >= nums[i-1]) {

                    dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];

                }

            }

        }

        return dp[m][target];

     }

 }

Idea 2. dynamic programming, 二维到一维的优化，注意在二维公式中sum的循环是从小到大（从左到右)，但是是前一行，转换成一维,需要用到前边的状态，所以要从右向左

dp[j] = dp[j] || dp[j-nums[i]]

dp[0] = true

Time complexity: O(n*target)

Space complexity: O(target)

 class Solution {

     public boolean canPartition(int[] nums) {

       int totalSum = 0;

       for(int num: nums) {

           totalSum += num;

       }

       if(totalSum % 2 != 0) {

           return false;

       }

       int target = totalSum/2;

       int n = nums.length;

       boolean[] dp = new boolean[target+1];

       dp[0] = true;

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

           for(int j = target; j >= nums[i]; --j) {

               dp[j] = dp[j] || dp[j-nums[i]];

           }

       }

       return dp[target];

     }

 }

巴特西

Partition Equal Subset Sum

最新文章

热门文章