Leetcode - 416. Partition Equal Subset Sum

문제

주어진 배열을 두개의 subset으로 나누었을때, 두 subset의 합이 같은 경우가 존재하는지 판단하라.
가령 아래 예의 경우 [1, 5, 5] 와 [11] 두개의 subset의 합이 동일해서 true이다.

Input: nums = [1,5,11,5]
Output: true
Input: nums = [1,2,3,5]
Output: false

아이디어

• 처음에 시도했던건 backtracking으로 1 ~ n개를 선택하는 모든 경우의수를 탐색하는거였음. 너무 비효율적 당연히 TLE
• DP방법은 해설을 조금 참고, 재귀적 관계 아이디어를 얻음.
• 마지막 인덱스 값부터 해당 인덱스를 선택하거나 안하거나 이 두가지 경우의 재귀호출을 하면된다.
  f(i, sum) = f(i - 1, sum - nums[i]) or f(i - 1, sum)
• 이런 형식의 재귀호출은 익숙치 않았다. 잘 기억하기!

해결 - brute force (TLE)

class Solution {
    
    bool dfs(vector<int> nums, int idx, int sum) {
        if (sum == 0)
            return true;
        if (idx < 0 || sum < 0)
            return false;
        return dfs(nums, idx - 1, sum - nums[idx]) || dfs(nums, idx - 1, sum);
    }
public:
    bool canPartition(vector<int>& nums) {
        int tot_sum = 0;
        for (auto it: nums)
            tot_sum += it;
        if (tot_sum % 2 == 0)
            tot_sum /= 2;
        else
            return false;
        return dfs(nums, nums.size() - 1, tot_sum);
    }
};

해결 DP top-down (memoization)

DFS with memoization

class Solution {
    vector<vector<int>> mem;
    bool dfs(vector<vector<int>> &mem, vector<int> nums, int idx, int sum) {
        if (sum == 0)
            return true;
        if (idx < 0 || sum < 0)
            return false;
        if (mem[idx][sum] != -1)
            return mem[idx][sum];
        
        mem[idx][sum] = dfs(mem, nums, idx - 1, sum - nums[idx]) || dfs(mem, nums, idx - 1, sum);
        return mem[idx][sum];
    }
public:
    bool canPartition(vector<int>& nums) {
        
        int tot_sum = 0;
        for (auto it: nums)
            tot_sum += it;
        if (tot_sum % 2 == 0)
            tot_sum /= 2;
        else
            return false;
        mem = vector<vector<int>>(nums.size() + 1, vector<int>(tot_sum + 1, -1));
        return dfs(mem, nums, nums.size() - 1, tot_sum);
    }
};