Equal Partition (Partition Equal Subset Sum)

🎯

Equal Partition (Partition Equal Subset Sum)

mediumDPAmazonFacebookGoogle

Imagine you have a collection of weights and want to split them into two groups with exactly the same total weight. Can you do it?

💡 This problem asks if a set can be split into two equal sum subsets. Beginners often struggle because it looks like a partition problem but requires understanding subset sums and dynamic programming to efficiently solve.

📋

Problem Statement

Given a non-empty array of positive integers nums, determine if it can be partitioned into two subsets such that the sum of elements in both subsets is equal. Return true if such a partition exists, otherwise false.

1 ≤ nums.length ≤ 2001 ≤ nums[i] ≤ 100

💡

Example

Input"[1, 5, 11, 5]"

Outputtrue

The array can be partitioned as [1, 5, 5] and [11], both summing to 11.

Input"[1, 2, 3, 5]"

Outputfalse

No partition exists that divides the array into two equal sum subsets.

• Single element array [1] → false
• All elements are the same [2, 2, 2, 2] → true
• Array with one very large element and small others [100, 1, 1, 1] → false
• Array with sum odd [1, 1, 3] → false

🔁

Why DP?

Why greedy fails:

A greedy approach might pick the largest elements first to form one subset, but this can fail. For example, nums = [1, 2, 5], greedy picks 5 first, but the rest sum to 3, so no equal partition exists. Greedy doesn't consider all combinations.

DP state:

dp[i][w] means whether it is possible to form a subset from the first i elements that sums exactly to w.

Recurrence:dp[i][w] = dp[i-1][w] OR dp[i-1][w - nums[i-1]] if w >= nums[i-1]

We can either exclude the current number and keep the sum w, or include it if it doesn't exceed w, and check if sum w - nums[i-1] was possible before.

⚠️

Common Mistakes

Not checking if total sum is even before proceeding

Wasted computation or incorrect true result

✅ Add early check: if total sum is odd, return false immediately

Iterating forwards in 1D DP causing reuse of elements

Incorrect results due to counting elements multiple times

✅ Iterate backwards in 1D DP to preserve 0/1 knapsack constraints

Using recursion without memoization on large inputs

Time limit exceeded due to exponential calls

✅ Add memoization to cache subproblem results

Confusing subset sum with partition sum, not halving total

Incorrect target sum leads to wrong answers

✅ Calculate target as half of total sum and solve subset sum for that

Not initializing dp[0] = True in tabulation

Algorithm fails to recognize sum 0 achievable, causing wrong results

✅ Set dp[i][0] = True for all i

🧠

Brute Force (Pure Recursion)

💡 Brute force explores all subsets to check if any sums to half the total. It is simple but inefficient, illustrating the problem's exponential nature and motivating DP.

Intuition

Try every subset by deciding for each element whether to include it or not, and check if any subset sums to half the total sum.

Algorithm

1. Calculate total sum and check if it's even; if not, return false immediately.
2. Recursively try including or excluding each element to find a subset summing to half the total.
3. If at any point the target sum is reached, return true.
4. If all elements are processed without reaching target, return false.

💡 The recursion tree grows exponentially because each element doubles the number of subsets to check.

Recurrence:f(i, sum) = f(i-1, sum) OR f(i-1, sum - nums[i-1])

</>

Code

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2

    def dfs(i, curr_sum):
        if curr_sum == target:
            return True
        if i == len(nums) or curr_sum > target:
            return False
        # Include nums[i]
        if dfs(i + 1, curr_sum + nums[i]):
            return True
        # Exclude nums[i]
        return dfs(i + 1, curr_sum)

    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(canPartition([1,5,11,5]))  # True
    print(canPartition([1,2,3,5]))   # False

Line Notes

total = sum(nums)Calculate total sum to determine if partition is possible

if total % 2 != 0:If total sum is odd, partition into equal subsets is impossible

def dfs(i, curr_sum):Recursive helper to explore subsets starting at index i

if curr_sum == target:Base case: found a subset summing to target

if i == len(nums) or curr_sum > target:Base case: no more elements or sum exceeded target

if dfs(i + 1, curr_sum + nums[i]):Try including current element

return dfs(i + 1, curr_sum)Try excluding current element

import java.util.*;
public class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        return dfs(nums, 0, 0, target);
    }

    private boolean dfs(int[] nums, int i, int currSum, int target) {
        if (currSum == target) return true;
        if (i == nums.length || currSum > target) return false;
        if (dfs(nums, i + 1, currSum + nums[i], target)) return true;
        return dfs(nums, i + 1, currSum, target);
    }

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

Line Notes

for (int num : nums) total += num;Sum all elements to check partition feasibility

if (total % 2 != 0) return false;Odd sum means no equal partition possible

private boolean dfs(int[] nums, int i, int currSum, int target)Recursive method exploring subsets

if (currSum == target) return true;Found valid subset

if (i == nums.length || currSum > target) return false;No more elements or sum exceeded

if (dfs(nums, i + 1, currSum + nums[i], target)) return true;Include current element

return dfs(nums, i + 1, currSum, target);Exclude current element

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        return dfs(nums, 0, 0, target);
    }

private:
    bool dfs(vector<int>& nums, int i, int currSum, int target) {
        if (currSum == target) return true;
        if (i == nums.size() || currSum > target) return false;
        if (dfs(nums, i + 1, currSum + nums[i], target)) return true;
        return dfs(nums, i + 1, currSum, target);
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1,5,11,5};
    vector<int> nums2 = {1,2,3,5};
    cout << boolalpha << sol.canPartition(nums1) << endl; // true
    cout << boolalpha << sol.canPartition(nums2) << endl; // false
    return 0;
}

Line Notes

for (int num : nums) total += num;Sum elements to check partition feasibility

if (total % 2 != 0) return false;Odd sum means no equal partition

bool dfs(vector<int>& nums, int i, int currSum, int target)Recursive helper to explore subsets

if (currSum == target) return true;Found subset with target sum

if (i == nums.size() || currSum > target) return false;No more elements or sum exceeded

if (dfs(nums, i + 1, currSum + nums[i], target)) return true;Include current element

return dfs(nums, i + 1, currSum, target);Exclude current element

function canPartition(nums) {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % 2 !== 0) return false;
    const target = total / 2;

    function dfs(i, currSum) {
        if (currSum === target) return true;
        if (i === nums.length || currSum > target) return false;
        if (dfs(i + 1, currSum + nums[i])) return true;
        return dfs(i + 1, currSum);
    }

    return dfs(0, 0);
}

// Example usage
console.log(canPartition([1,5,11,5])); // true
console.log(canPartition([1,2,3,5]));  // false

Line Notes

const total = nums.reduce((a, b) => a + b, 0);Calculate total sum to check feasibility

if (total % 2 !== 0) return false;Odd sum means no equal partition

function dfs(i, currSum)Recursive helper exploring subsets

if (currSum === target) return true;Found valid subset

if (i === nums.length || currSum > target) return false;No more elements or sum exceeded

if (dfs(i + 1, currSum + nums[i])) return true;Include current element

return dfs(i + 1, currSum);Exclude current element

⏱

Complexity

TimeO(2^n)

SpaceO(n) recursion stack

Each element can be included or excluded, leading to 2^n subsets to check.

💡 For n=20, this means over a million subsets, which is too slow for interviews.

Interview Verdict: TLE / Use only to introduce problem and motivate DP

Brute force is too slow for large inputs but helps understand the problem structure.

🧠

Top-Down Memoization (Recursion + Caching)

💡 Memoization caches results of subproblems to avoid repeated work, drastically improving brute force efficiency.

Intuition

Use recursion but store results for each index and current sum to prevent recomputation.

Algorithm

1. Calculate total sum and check if even; return false if odd.
2. Use a recursive helper with memo to store results for (index, current sum).
3. At each step, try including or excluding current element.
4. Return true if target sum is reached; otherwise false.

💡 Memoization prunes the recursion tree by remembering solved states, reducing exponential calls.

Recurrence:f(i, sum) = f(i-1, sum) OR f(i-1, sum - nums[i-1]) with memoization

</>

Code

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    memo = {}

    def dfs(i, curr_sum):
        if curr_sum == target:
            return True
        if i == len(nums) or curr_sum > target:
            return False
        if (i, curr_sum) in memo:
            return memo[(i, curr_sum)]
        include = dfs(i + 1, curr_sum + nums[i])
        exclude = dfs(i + 1, curr_sum)
        memo[(i, curr_sum)] = include or exclude
        return memo[(i, curr_sum)]

    return dfs(0, 0)

# Example usage
if __name__ == '__main__':
    print(canPartition([1,5,11,5]))  # True
    print(canPartition([1,2,3,5]))   # False

Line Notes

memo = {}Initialize cache to store results of subproblems

if (i, curr_sum) in memo:Return cached result if subproblem already solved

memo[(i, curr_sum)] = include or excludeStore result to avoid recomputation

include = dfs(i + 1, curr_sum + nums[i])Try including current element

exclude = dfs(i + 1, curr_sum)Try excluding current element

import java.util.*;
public class Solution {
    private Map<String, Boolean> memo = new HashMap<>();

    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        return dfs(nums, 0, 0, target);
    }

    private boolean dfs(int[] nums, int i, int currSum, int target) {
        if (currSum == target) return true;
        if (i == nums.length || currSum > target) return false;
        String key = i + "," + currSum;
        if (memo.containsKey(key)) return memo.get(key);
        boolean include = dfs(nums, i + 1, currSum + nums[i], target);
        boolean exclude = dfs(nums, i + 1, currSum, target);
        memo.put(key, include || exclude);
        return memo.get(key);
    }

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

Line Notes

private Map<String, Boolean> memo = new HashMap<>();Cache results of subproblems using string keys

String key = i + "," + currSum;Create unique key for current state

if (memo.containsKey(key)) return memo.get(key);Return cached result if available

memo.put(key, include || exclude);Store computed result

boolean include = dfs(nums, i + 1, currSum + nums[i], target);Try including current element

boolean exclude = dfs(nums, i + 1, currSum, target);Try excluding current element

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution {
    unordered_map<string, bool> memo;
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        return dfs(nums, 0, 0, target);
    }

private:
    bool dfs(vector<int>& nums, int i, int currSum, int target) {
        if (currSum == target) return true;
        if (i == nums.size() || currSum > target) return false;
        string key = to_string(i) + "," + to_string(currSum);
        if (memo.count(key)) return memo[key];
        bool include = dfs(nums, i + 1, currSum + nums[i], target);
        bool exclude = dfs(nums, i + 1, currSum, target);
        memo[key] = include || exclude;
        return memo[key];
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1,5,11,5};
    vector<int> nums2 = {1,2,3,5};
    cout << boolalpha << sol.canPartition(nums1) << endl; // true
    cout << boolalpha << sol.canPartition(nums2) << endl; // false
    return 0;
}

Line Notes

unordered_map<string, bool> memo;Cache subproblem results with string keys

string key = to_string(i) + "," + to_string(currSum);Create unique key for current state

if (memo.count(key)) return memo[key];Return cached result if exists

memo[key] = include || exclude;Store computed result

bool include = dfs(nums, i + 1, currSum + nums[i], target);Try including current element

bool exclude = dfs(nums, i + 1, currSum, target);Try excluding current element

function canPartition(nums) {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % 2 !== 0) return false;
    const target = total / 2;
    const memo = new Map();

    function dfs(i, currSum) {
        if (currSum === target) return true;
        if (i === nums.length || currSum > target) return false;
        const key = i + ',' + currSum;
        if (memo.has(key)) return memo.get(key);
        const include = dfs(i + 1, currSum + nums[i]);
        const exclude = dfs(i + 1, currSum);
        memo.set(key, include || exclude);
        return memo.get(key);
    }

    return dfs(0, 0);
}

// Example usage
console.log(canPartition([1,5,11,5])); // true
console.log(canPartition([1,2,3,5]));  // false

Line Notes

const memo = new Map();Cache results of subproblems

const key = i + ',' + currSum;Create unique key for memoization

if (memo.has(key)) return memo.get(key);Return cached result if available

memo.set(key, include || exclude);Store computed result

const include = dfs(i + 1, currSum + nums[i]);Try including current element

const exclude = dfs(i + 1, currSum);Try excluding current element

⏱

Complexity

TimeO(n * target)

SpaceO(n * target) for memo

Memoization reduces exponential calls to polynomial by caching states defined by index and sum.

💡 For n=20 and target=1000, this is about 20,000 operations, which is efficient.

Interview Verdict: Accepted - efficient for given constraints

Memoization is a practical optimization that makes the problem solvable within time limits.

🧠

Bottom-Up Tabulation (2D DP Table)

💡 Tabulation builds the solution iteratively from smaller subproblems, making the process explicit and often easier to debug.

Intuition

Create a 2D boolean DP table where dp[i][w] indicates if sum w can be formed using first i elements.

Algorithm

1. Calculate total sum and check if even; return false if odd.
2. Initialize dp table with dp[0][0] = True (sum 0 with 0 elements).
3. Iterate over elements and sums, updating dp[i][w] based on previous row.
4. Return dp[n][target] indicating if target sum is achievable.

💡 Tabulation avoids recursion and explicitly shows how solutions build up from smaller problems.

Recurrence:dp[i][w] = dp[i-1][w] OR dp[i-1][w - nums[i-1]] if w >= nums[i-1]

</>

Code

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[i][0] = True

    for i in range(1, n + 1):
        for w in range(1, target + 1):
            if w < nums[i - 1]:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = dp[i - 1][w] or dp[i - 1][w - nums[i - 1]]

    return dp[n][target]

# Example usage
if __name__ == '__main__':
    print(canPartition([1,5,11,5]))  # True
    print(canPartition([1,2,3,5]))   # False

Line Notes

dp = [[False] * (target + 1) for _ in range(n + 1)]Create DP table with dimensions (n+1) x (target+1)

for i in range(n + 1): dp[i][0] = TrueSum 0 is always achievable with empty subset

if w < nums[i - 1]: dp[i][w] = dp[i - 1][w]Cannot include current element if it exceeds sum w

else: dp[i][w] = dp[i - 1][w] or dp[i - 1][w - nums[i - 1]]Include or exclude current element to form sum w

return dp[n][target]Final answer: can target sum be formed using all elements

import java.util.*;
public class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        int n = nums.length;
        boolean[][] dp = new boolean[n + 1][target + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= target; w++) {
                if (w < nums[i - 1]) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }

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

Line Notes

boolean[][] dp = new boolean[n + 1][target + 1];DP table for subset sums

for (int i = 0; i <= n; i++) dp[i][0] = true;Sum 0 achievable with empty subset

if (w < nums[i - 1]) dp[i][w] = dp[i - 1][w];Cannot include element if too large

else dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];Include or exclude element

return dp[n][target];Final answer

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        int n = nums.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
        for (int i = 0; i <= n; i++) dp[i][0] = true;

        for (int i = 1; i <= n; i++) {
            for (int w = 1; w <= target; w++) {
                if (w < nums[i - 1]) {
                    dp[i][w] = dp[i - 1][w];
                } else {
                    dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];
                }
            }
        }
        return dp[n][target];
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1,5,11,5};
    vector<int> nums2 = {1,2,3,5};
    cout << boolalpha << sol.canPartition(nums1) << endl; // true
    cout << boolalpha << sol.canPartition(nums2) << endl; // false
    return 0;
}

Line Notes

vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));2D DP table initialization

for (int i = 0; i <= n; i++) dp[i][0] = true;Sum 0 achievable with empty subset

if (w < nums[i - 1]) dp[i][w] = dp[i - 1][w];Exclude element if too large

else dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];Include or exclude element

return dp[n][target];Final answer

function canPartition(nums) {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % 2 !== 0) return false;
    const target = total / 2;
    const n = nums.length;
    const dp = Array.from({ length: n + 1 }, () => Array(target + 1).fill(false));
    for (let i = 0; i <= n; i++) dp[i][0] = true;

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= target; w++) {
            if (w < nums[i - 1]) {
                dp[i][w] = dp[i - 1][w];
            } else {
                dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];
            }
        }
    }
    return dp[n][target];
}

// Example usage
console.log(canPartition([1,5,11,5])); // true
console.log(canPartition([1,2,3,5]));  // false

Line Notes

const dp = Array.from({ length: n + 1 }, () => Array(target + 1).fill(false));Initialize 2D DP array

for (let i = 0; i <= n; i++) dp[i][0] = true;Sum 0 achievable with empty subset

if (w < nums[i - 1]) dp[i][w] = dp[i - 1][w];Exclude element if too large

else dp[i][w] = dp[i - 1][w] || dp[i - 1][w - nums[i - 1]];Include or exclude element

return dp[n][target];Final answer

⏱

Complexity

TimeO(n * target)

SpaceO(n * target)

We fill a table of size n by target, each cell computed once.

💡 For n=20 and target=1000, about 20,000 operations, efficient for interviews.

Interview Verdict: Accepted - clear and efficient iterative solution

Tabulation is often preferred for clarity and iterative control.

🧠

Space Optimized Bottom-Up (1D DP Array)

💡 We can reduce space by using a 1D array and iterating backwards to avoid overwriting needed values.

Intuition

Use a 1D boolean array where dp[w] indicates if sum w is achievable. Update dp in reverse to simulate 2D table.

Algorithm

1. Calculate total sum and check if even; return false if odd.
2. Initialize 1D dp array with dp[0] = True.
3. For each number, iterate backwards through dp updating dp[w] = dp[w] OR dp[w - num] if w >= num.
4. Return dp[target] indicating if target sum is achievable.

💡 Backward iteration ensures each element is only counted once per iteration, preserving 0/1 knapsack constraints.

Recurrence:dp[w] = dp[w] OR dp[w - nums[i]]

</>

Code

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for w in range(target, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]

# Example usage
if __name__ == '__main__':
    print(canPartition([1,5,11,5]))  # True
    print(canPartition([1,2,3,5]))   # False

Line Notes

dp = [False] * (target + 1)Initialize 1D DP array for sums up to target

dp[0] = TrueSum 0 is always achievable with empty subset

for w in range(target, num - 1, -1)Iterate backwards to avoid reusing elements in same iteration

dp[w] = dp[w] or dp[w - num]Update dp[w] if sum w can be formed including current num

return dp[target]Final answer: can target sum be formed

public class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int w = target; w >= num; w--) {
                dp[w] = dp[w] || dp[w - num];
            }
        }
        return dp[target];
    }

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

Line Notes

boolean[] dp = new boolean[target + 1];1D DP array for sums

dp[0] = true;Sum 0 achievable with empty subset

for (int w = target; w >= num; w--)Backward iteration to avoid reuse

dp[w] = dp[w] || dp[w - num];Update dp for current sum

return dp[target];Final answer

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = 0;
        for (int num : nums) total += num;
        if (total % 2 != 0) return false;
        int target = total / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int num : nums) {
            for (int w = target; w >= num; w--) {
                dp[w] = dp[w] || dp[w - num];
            }
        }
        return dp[target];
    }
};

int main() {
    Solution sol;
    vector<int> nums1 = {1,5,11,5};
    vector<int> nums2 = {1,2,3,5};
    cout << boolalpha << sol.canPartition(nums1) << endl; // true
    cout << boolalpha << sol.canPartition(nums2) << endl; // false
    return 0;
}

Line Notes

vector<bool> dp(target + 1, false);1D DP array initialization

dp[0] = true;Sum 0 achievable with empty subset

for (int w = target; w >= num; w--)Backward iteration to prevent reuse

dp[w] = dp[w] || dp[w - num];Update dp for sum w

return dp[target];Final answer

function canPartition(nums) {
    const total = nums.reduce((a, b) => a + b, 0);
    if (total % 2 !== 0) return false;
    const target = total / 2;
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;

    for (const num of nums) {
        for (let w = target; w >= num; w--) {
            dp[w] = dp[w] || dp[w - num];
        }
    }
    return dp[target];
}

// Example usage
console.log(canPartition([1,5,11,5])); // true
console.log(canPartition([1,2,3,5]));  // false

Line Notes

const dp = new Array(target + 1).fill(false);Initialize 1D DP array

dp[0] = true;Sum 0 achievable with empty subset

for (let w = target; w >= num; w--)Backward iteration to avoid reuse

dp[w] = dp[w] || dp[w - num];Update dp for sum w

return dp[target];Final answer

⏱

Complexity

TimeO(n * target)

SpaceO(target)

Only one array of size target+1 is maintained and updated for each element.

💡 For n=20 and target=1000, this uses much less memory while maintaining efficiency.

Interview Verdict: Accepted - optimal space and time

This is the best practical solution for interviews, balancing clarity and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Use memoization or tabulation in interviews; space optimized DP is best if comfortable.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	Yes	Mention only - never code
2. Top-Down Memoization	O(n * target)	O(n * target) memo + recursion stack	Possible but less likely	Yes	Good first coding approach
3. Bottom-Up Tabulation	O(n * target)	O(n * target)	No	Yes	Preferred iterative solution
4. Space Optimized Bottom-Up	O(n * target)	O(target)	No	No (without extra work)	Best for follow-up or optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare for common follow-ups.

How to Present

Clarify problem constraints and input size.Explain brute force recursion to show problem nature.Introduce memoization to optimize recursion.Present bottom-up tabulation for iterative clarity.Discuss space optimization as a final improvement.Write clean code and test with examples.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Understanding of subset sum DP, ability to optimize naive solutions, and knowledge of space optimization.

Common Follow-ups

• Can you optimize space complexity? → Use 1D DP array with backward iteration.
• What if numbers can be negative? → Problem changes; standard DP may not apply directly.

💡 These follow-ups test deeper understanding of DP and problem constraints.

🔍

Pattern Recognition

When to Use

1) Problem asks if array can be split into equal sum subsets, 2) Involves subset sums, 3) Requires boolean DP, 4) Constraints fit knapsack pattern

Signature Phrases

'partition into two subsets with equal sum''subset sum equals half of total sum'

NOT This Pattern When

Problems involving unbounded knapsack or continuous values are different patterns.

Similar Problems

Subset Sum Problem - core boolean DP problemPartition to K Equal Sum Subsets - generalizes equal partitionTarget Sum - related DP problem involving subset sums

Practice

1. Consider the following Python code for counting the number of ways to make change. What is the output when calling change(5, [1, 2, 5])?

easy

A. 5

B. 3

C. 4

D. 6

Solution

1. Step 1: Initialize dp array

   dp = [1,0,0,0,0,0] since dp[0]=1.

2. Step 2: Update dp for each coin

   For coin=1: dp becomes [1,1,1,1,1,1]; for coin=2: dp updates to [1,1,2,2,3,3]; for coin=5: dp updates to [1,1,2,2,3,4].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   dp[5] = 4 matches known output [OK]

Hint: Trace dp updates coin by coin [OK]

Common Mistakes:

• Off-by-one in dp indexing
• Confusing permutations with combinations

2. You are given a list of jobs where each job has a start time, an end time, and a profit. You want to schedule jobs to maximize total profit such that no two jobs overlap. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming with jobs sorted by end time and binary search to find compatible jobs

B. Pure brute force recursion checking all subsets of jobs

C. Greedy algorithm that always picks the job with the earliest end time

D. Dynamic programming based on sorting jobs by start time and using prefix sums

Solution

1. Step 1: Understand job scheduling constraints

   The problem requires selecting non-overlapping jobs to maximize profit, which is a classic weighted interval scheduling problem.

2. Step 2: Identify the optimal approach

   Sorting jobs by end time allows binary searching for the last compatible job, enabling a DP solution that builds optimal profit incrementally.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy fails on overlapping jobs with higher profit; DP with binary search handles all cases optimally [OK]

Hint: Sort by end time and use DP with binary search [OK]

Common Mistakes:

• Assuming greedy by earliest end time always works
• Sorting by start time only
• Trying brute force without pruning

3. What is the time complexity of the bottom-up dynamic programming solution for the Perfect Squares problem using the unbounded knapsack pattern, where n is the input number?

medium

A. O(n^2)

B. O(sqrt(n) * log n)

C. O(n * log n)

D. O(n * sqrt(n))

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop runs from 1 to n (O(n)). The inner loop iterates over all perfect squares less than or equal to i, which is approximately O(sqrt(n)) because the largest square root is about sqrt(n).

2. Step 2: Combine complexities

   Multiplying outer and inner loops gives O(n * sqrt(n)). Other options either overestimate (O(n^2)) or underestimate (O(n log n), O(sqrt(n) log n)) the complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops: n and sqrt(n) -> O(n * sqrt(n)) [OK]

Hint: Inner loop runs up to sqrt(n), outer up to n [OK]

Common Mistakes:

• Assuming inner loop is O(n)
• Confusing recursion stack space with DP space

4. What is the time complexity of the space-optimized bottom-up subset sum algorithm given an input list of size n and target sum S?

medium

A. O(2^n)

B. O(n + S)

C. O(n * S)

D. O(n * log S)

Solution

1. Step 1: Identify loops in the algorithm

   The algorithm has an outer loop over n elements and an inner loop over sums from S down to each num.

2. Step 2: Calculate total operations

   Each element causes up to S iterations, so total time is O(n * S). Recursive brute force is exponential, and linear or log factors are incorrect.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Nested loops over n and S -> O(n * S) [OK]

Hint: Nested loops over n and S -> multiply complexities [OK]

Common Mistakes:

• Confusing recursion stack space with time
• Assuming linear or exponential time incorrectly

5. The following code attempts to solve the Target Sum problem using bottom-up DP with offset indexing. Which line contains a subtle bug that causes incorrect results on inputs containing zero?

medium

A. Line 12-15: Updating dp array in-place instead of using a separate next_dp

B. Line 6: dp[offset] = 1

C. Line 10: if dp[s] != 0:

D. Line 8: for num in nums:

Solution

1. Step 1: Identify DP update method

   The code updates dp in-place during iteration over sums, causing double counting when num=0 or overlapping states.

2. Step 2: Understand impact on zero values

   Zero does not change sum, so updating dp in-place doubles counts incorrectly. Using a separate next_dp array avoids this.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place updates cause state reuse within iteration, breaking correctness [OK]

Hint: In-place dp updates cause double counting with zero values [OK]

Common Mistakes:

• Not using a separate dp array for next iteration