Leetcode — 416. Partition Equal Subset Sum (中文)

問題連結: https://leetcode.com/problems/partition-equal-subset-sum/

給予一正整數陣列 nums , 求回傳這個陣列是否可以劃分成兩個數字總和相同的集合

條件:

• 1 <= nums.length <= 200
• 1 <= nums[i] <= 100

範例: 
Input: nums = [1,5,11,5]
Output: true
Explanation: 可把陣列數字分成 [1, 5, 5] 和 [11] 兩組, 總和皆為11

想法:

我的第一個想法是, 我們要試著找到兩個集合, 且這兩個集合的數字總和皆為整個陣列數字總合的一半, 而這個目標其實也可以解釋成, 我們只要找到一個符合這個條件的集合就可以了! 因為當我們找到一個集合的數字總和是x的話, 代表剩下數字的總和也一定是x (因此全部總和才會是2x)
所以現在問題感覺又可以簡化一點, 變成我們只要從一開始陣列找到可以組合成目標總和的幾個數字就可以; 我們甚至可以在一開始如果發現總和不能被2整除的時候, 就直接回傳false, 結束程式

檢查完一些必要的特殊案例(例如不能被2整除, 陣列只有一個數字), 我們可以把問題變成 — 回傳我們可否在陣列中組合幾個數字, 讓他們總和為x

因為所有的數字都會在範圍1~100而已, 我在想我們是不是可以直接用backtracking來解這題, 我們可以選陣列中的一個數字, 因此目標總和也有所改變, 我們就會再試著看我們是否可以用剩餘數字找到新的目標總和, 重複同樣動作; 如果這個數字不行, 我們則會刪掉這個數字, 再找下個可行數字

那我們來看看如何用這個想法來解這題 👉

程式邏輯:

在我們開始做backtracking之前, 我們需要先準備我們需要的資料 — 我們的目標總和, 以及一個map陣列, 將存著各數字在一開始給予的陣列中出現的次數 (所以代表在一開始的陣列中, 我們有map[i]個數字i)

那我們真正的第一步就是, 做一個假設, 假設我們陣列之中最大的數字就在我們要找的集合當中 (畢竟這個數字一定會在任一結果集合中)
而會這樣假設則是因為我們想要減少搜尋目標總和的時間, 因此若一開始就找一個大數字, 之後我們要湊目標總和的速度就會比較快一點, 所以也可以想成因為結果有兩個集合, 因此我們想要湊的是 有最大數字的那個集合

我們將會有一個helper method負責回傳我們可否在現在剩下的數字當中湊到我們的目標總和
而在helper method裡面, 我們會做的事情就是取數字, 然後再試試看剩下的數字可否組成 新的目標總和; 若不行, 則就取消選那個數字, 改選下一個數字
一個特點是我們這邊選數字也都是從 我們可以選的最大數字來選, 也是為了節省時間
⚠️而我們說的"可以選的最大數字" 指的就是, 比目標總和跟100(我們的map中可容許最大數字)小的最大數字

public boolean canPartition(int[] nums) {
        int sum = 0;
        int[] map = new int[101];
        int max = 0;
        for(int num: nums)
        {
            sum += num;
            map[num]++;
            max = Math.max(max, num);
        }
        if(sum%2==1 || nums.length==1)
            return false;
        
        sum/=2;
        map[max]--;
        return helper(map, sum-max);
    }
    public boolean helper(int[] map, int target){
        if(target<0)
            return false;
        if(target==0) 
            return true;
        int max = Math.min(100,target);
        for(int i=max;i>=0;i--)
        {
            if(map[i]==0)
                continue;
            map[i]--; //choose number i
            if(helper(map, target-i))
                return true;
            map[i]++; //redo
        }
        return false;
    }

而上述的程式碼會在大部分Leetcode上的test cases因 Time Limit Exceeded而失敗, 這是因為我們可能重複的一直去試著找同樣的目標總和
因此, 我們需要再多加個變數去儲存我們嘗試找過但失敗的目標總和 來解決這個問題

以下為2ms的程式碼, 贏過 98% —

public boolean canPartition(int[] nums) {
        int sum = 0;
        int[] map = new int[101];
        int max = 0;
        for(int num: nums)
        {
            sum += num;
            map[num]++;
            max = Math.max(max, num);
        }
        if(sum%2==1 || nums.length==1)
            return false;
        
        sum/=2;
        map[max]--;
        return helper(map, sum-max, new HashSet<>());
    }
    public boolean helper(int[] map, int target, Set<Integer> failed){
        if(target<0 || failed.contains(target))
            return false;
        if(target==0)
            return true;
        
        int max = Math.min(100,target);
        for(int i=max;i>=0;i--)
        {
            if(map[i]==0)
                continue;
            map[i]--;
            if(helper(map, target-i, failed))
                return true;
            map[i]++;
        }
        failed.add(target);
        return false;
    }