Partition Subset Sum

Problem Statement

Given an array of integers nums, return true if it can be partitioned into two subsets such that the sum of elements in both subsets is equal. Otherwise, return false. leetcode

Key Insight

To split the array into two equal subsets, the total sum of the array must be even. So, the problem reduces to checking whether there exists a subset with sum = totalSum / 2.

Recursive Insight

We define a recursive function:

Copybool f(int index, int target)

• index is the current index in the array.

• target is the remaining sum we want to achieve.

At each step, we either include or exclude the current element:

• Include nums[index] → reduce target by nums[index].

• Exclude nums[index] → move to next index without changing target.

Brute Force (Recursion)

Copybool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;

    int target = total / 2;
    return dfs(nums, 0, target);
}

bool dfs(vector<int>& nums, int index, int target) {
    if (target == 0) return true;
    if (index >= nums.size() || target < 0) return false;

    // Try not picking or picking the current element
    return dfs(nums, index + 1, target) || dfs(nums, index + 1, target - nums[index]);
}

• Time Complexity: Exponential O(2^n)

• Space Complexity: O(n) recursive stack

Optimized: Memoization (Top-Down DP)

Copybool canPartition(vector<int>& nums) {
    int total = accumulate(nums.begin(), nums.end(), 0);
    if (total % 2 != 0) return false;

    int target = total / 2;
    vector<vector<int>> dp(nums.size(), vector<int>(target + 1, -1));
    return dfs(nums, 0, target, dp);
}

bool dfs(vector<int>& nums, int index, int target, vector<vector<int>>& dp) {
    if (target == 0) return true;
    if (index >= nums.size() || target < 0) return false;

    if (dp[index][target] != -1)
        return dp[index][target];

    bool notPick = dfs(nums, index + 1, target, dp);
    bool pick = dfs(nums, index + 1, target - nums[index], dp);

    return dp[index][target] = pick || notPick;
}

• Time Complexity: O(n * target)

• Space Complexity: O(n * target) for memo table + recursive stack