【力扣】416. 分割等和子集

給你一個(gè) 只包含正整數(shù)的非空數(shù)組 nums 。請(qǐng)你判斷是否可以將這個(gè)數(shù)組分割成兩個(gè)子集，使得兩個(gè)子集的元素和相等。

示例 1：
輸入：nums = [1,5,11,5]
輸出：true
解釋：數(shù)組可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
輸入：nums = [1,2,3,5]
輸出：false
解釋：數(shù)組不能分割成兩個(gè)元素和相等的子集。

提示：
1 <= nums.length <= 200
1 <= nums[i] <= 100

題解

動(dòng)態(tài)規(guī)劃

01背包問(wèn)題：有 N 件物品和一個(gè)最多能背重量為 W 的背包。第 i 件物品的重量是weight[i]，得到的價(jià)值是value[i] 。每件物品只能用一次，求解將哪些物品裝入背包里物品價(jià)值總和最大。

• 背包的體積為sum / 2
• 背包要放入的商品（集合里的元素）重量為元素的數(shù)值，價(jià)值也為元素的數(shù)值
• 背包如果正好裝滿，說(shuō)明找到了總和為 sum / 2 的子集
• 背包中每一個(gè)元素是不可重復(fù)放入

回溯五步：

• 確定dp數(shù)組以及下標(biāo)的含義
  01背包中，dp[j] 表示： 容量為 j 的背包，所背的物品價(jià)值最大可以為 dp[j]
  本題中每一個(gè)元素的數(shù)值既是重量，也是價(jià)值。
  dp[j] 表示背包總?cè)萘浚ㄋ苎b的總重量）是 j，放進(jìn)物品后，背的最大重量為 dp[j]
  如果背包容量為 target， dp[target] 就是裝滿背包之后的重量，所以 當(dāng) dp[target] == target 的時(shí)候，背包就裝滿了。
• 確定遞推公式
  01背包的遞推公式為：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  背包里放入數(shù)值，那么物品 i 的重量是 nums[i]，其價(jià)值也是 nums[i]。
  所以遞推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
• dp數(shù)組如何初始化
  dp[j] 的定義來(lái)看，首先dp[0]一定是0，如果題目給的價(jià)值都是正整數(shù)那么非0下標(biāo)都初始化為0就可以了，如果題目給的價(jià)值有負(fù)數(shù)，那么非0下標(biāo)就要初始化為負(fù)無(wú)窮。
• 確定遍歷順序
  如果使用一維 dp數(shù)組，物品遍歷的 for 循環(huán)放在外層，遍歷背包的for循環(huán)放在內(nèi)層，且內(nèi)層 for 循環(huán)倒序遍歷。
• 舉例推導(dǎo)dp數(shù)組
  dp[j] == j 說(shuō)明，集合中的子集總和正好可以湊成總和 j
  

class B {
    public boolean canPartition(int[] nums) {
        if(nums == null || nums.length == 0) {
            return false;
        }
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        //總和為奇數(shù)，不能平分
        if(sum % 2 != 0) {
            return false;
        }
        
        int target = sum / 2;
        int[] dp = new int[target + 1];
        
        for(int i = 0; i < nums.length; i++) {
            for(int j = target; j >= nums[i]; j--) {
                //物品 i 的重量是 nums[i]，其價(jià)值也是 nums[i]
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            //剪枝一下，每一次完成內(nèi)層的for-loop，立即檢查是否dp[target] == target，優(yōu)化時(shí)間復(fù)雜度（26ms -> 20ms）
            if(dp[target] == target)
                return true;
        }
        return dp[target] == target;
    }
}

回溯（會(huì)超時(shí)）

取與不取文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-692026.html

class B {
    public static void main(String[] args) {
        B b = new B();
        int[] nums = {1,5,11,5};//true
//        int[] nums = {1,2,3,5};//false
        System.out.println(b.canPartition(nums));
    }

    // 回溯
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public boolean canPartition(int[] nums) {
        int target = 0;
        for (int i = 0; i < nums.length; i++) {
            target += nums[i];
        }
        if (target % 2 != 0) {
            return false;
        }

        target = target / 2;
        //Arrays.sort(nums);
        trace(nums, 0, target, 0);

        if (res.size() > 0) {
            // System.out.println(res);
            return true;
        } else {
            return false;
        }
    }

    public void trace(int[] nums, int start, int target, int sum) {
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        if (sum > target) {
            return;
        }
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            sum += nums[i];
            trace(nums, i + 1, target, sum);
            sum -= nums[i];
            path.remove(path.size() - 1);
        }
    }
}

到了這里，關(guān)于【力扣】416. 分割等和子集 ＜動(dòng)態(tài)規(guī)劃、回溯＞的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！