Perfect Squares

🎯

Perfect Squares

mediumDPGoogleAmazon

Imagine you want to represent a number as a sum of perfect squares, like breaking a chocolate bar into square pieces with minimal cuts.

💡 This problem asks for the minimum number of perfect square numbers that sum to a given integer n. Beginners often struggle because it looks like a math problem but is best solved with dynamic programming due to overlapping subproblems and the need to minimize counts.

📋

Problem Statement

Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer (e.g., 1, 4, 9, 16, ...). Input: integer n. Output: integer representing the minimum count of perfect squares summing to n.

1 ≤ n ≤ 10^5

💡

Example

Input"n = 12"

Output3

12 = 4 + 4 + 4 (three perfect squares)

Input"n = 13"

Output2

13 = 4 + 9 (two perfect squares)

• n = 1 → output 1 (smallest input)
• n = 0 → output 0 (no squares needed)
• n = 10000 → output 1 (perfect square itself)
• n = 2 → output 2 (1 + 1, smallest non-square sum)

🔁

Why DP?

Why greedy fails:

Greedy fails because choosing the largest square first does not always yield the minimal count. For example, n=12: greedy picks 9 first, then 3 leftover, which needs 3 ones, total 4 squares. But optimal is 4+4+4 = 3 squares.

DP state:

dp[i] represents the minimum number of perfect squares that sum to the integer i.

Recurrence:dp[i] = min(dp[i], 1 + dp[i - j*j]) for all j where j*j <= i

For each number i, try subtracting every perfect square j*j less than or equal to i, and pick the minimal count among those options plus one for the chosen square.

⚠️

Common Mistakes

Not handling base case dp[0] = 0

Leads to incorrect results or infinite loops

✅ Explicitly set dp[0] = 0 before loops

Using greedy approach picking largest square first

Produces suboptimal results, e.g., n=12 returns 4 instead of 3

✅ Use DP to explore all squares, not just largest

Not memoizing recursive calls

Causes TLE due to exponential recomputation

✅ Add memoization cache to store results

Iterating over squares incorrectly (e.g., j*j > n)

Index errors or missing valid squares

✅ Ensure loop condition j*j <= current target

Using 2D DP unnecessarily

Wastes space and complicates solution

✅ Use 1D DP since only sum matters, not order

🧠

Brute Force (Pure Recursion)

💡 Starting with brute force helps understand the problem's recursive structure and why naive recursion is inefficient due to repeated calculations.

Intuition

Try every perfect square less than or equal to n, recursively find minimal counts for the remainder, and pick the minimum among them.

Algorithm

1. If n is zero, return 0 because no squares are needed.
2. For each perfect square less than or equal to n, recursively compute the minimal count for n minus that square.
3. Return the minimum count found plus one for the chosen square.
4. Explore all possibilities to find the global minimum.

💡 The recursion tree grows exponentially because it tries all square partitions without remembering results.

Recurrence:f(n) = min_{j*j ≤ n} (1 + f(n - j*j))

</>

Code

def numSquares(n):
    def helper(k):
        if k == 0:
            return 0
        res = float('inf')
        j = 1
        while j*j <= k:
            res = min(res, 1 + helper(k - j*j))
            j += 1
        return res
    return helper(n)

# Example usage
if __name__ == '__main__':
    print(numSquares(12))  # Output: 3

Line Notes

def helper(k):Defines the recursive helper function to compute minimal squares for k

if k == 0:Base case: zero requires zero squares

while j*j <= k:Iterate over all perfect squares less than or equal to k

res = min(res, 1 + helper(k - j*j))Try choosing square j*j and recurse for remainder, update minimal count

public class Solution {
    public int numSquares(int n) {
        return helper(n);
    }
    private int helper(int k) {
        if (k == 0) return 0;
        int res = Integer.MAX_VALUE;
        for (int j = 1; j*j <= k; j++) {
            res = Math.min(res, 1 + helper(k - j*j));
        }
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numSquares(12)); // Output: 3
    }
}

Line Notes

public int helper(int k)Recursive helper to compute minimal squares for k

if (k == 0) return 0;Base case: zero requires zero squares

for (int j = 1; j*j <= k; j++)Iterate over all perfect squares ≤ k

res = Math.min(res, 1 + helper(k - j*j));Try choosing square j*j and recurse for remainder

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

int helper(int k) {
    if (k == 0) return 0;
    int res = INT_MAX;
    for (int j = 1; j*j <= k; j++) {
        res = min(res, 1 + helper(k - j*j));
    }
    return res;
}

int numSquares(int n) {
    return helper(n);
}

int main() {
    cout << numSquares(12) << endl; // Output: 3
    return 0;
}

Line Notes

int helper(int k)Recursive helper function for minimal squares count

if (k == 0) return 0;Base case for recursion

for (int j = 1; j*j <= k; j++)Loop over all perfect squares ≤ k

res = min(res, 1 + helper(k - j*j));Try each square and recurse for remainder

function numSquares(n) {
    function helper(k) {
        if (k === 0) return 0;
        let res = Infinity;
        for (let j = 1; j*j <= k; j++) {
            res = Math.min(res, 1 + helper(k - j*j));
        }
        return res;
    }
    return helper(n);
}

console.log(numSquares(12)); // Output: 3

Line Notes

function helper(k)Recursive helper to compute minimal squares for k

if (k === 0) return 0;Base case: zero requires zero squares

for (let j = 1; j*j <= k; j++)Iterate over all perfect squares ≤ k

res = Math.min(res, 1 + helper(k - j*j));Try choosing square j*j and recurse for remainder

⏱

Complexity

TimeO(2^n) exponential due to repeated recursive calls

SpaceO(n) recursion stack depth

Each call branches into multiple calls for smaller n, causing exponential growth

💡 For n=12, this means hundreds of calls; for n=20, thousands, making it impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's recursive nature.

🧠

Top-Down Memoization

💡 Memoization caches results of recursive calls to avoid recomputation, drastically improving efficiency while preserving the recursive intuition.

Intuition

Store results for each subproblem n in a cache so repeated calls return instantly, reducing exponential to polynomial time.

Algorithm

1. Initialize a cache (dictionary or array) to store results for subproblems.
2. If n is zero, return 0.
3. If result for n is cached, return it immediately.
4. Otherwise, compute minimal count recursively and store in cache before returning.

💡 Memoization avoids repeated work by remembering previous results, turning exponential recursion into polynomial time.

Recurrence:f(n) = min_{j*j ≤ n} (1 + f(n - j*j)) with memoization

</>

Code

def numSquares(n):
    memo = {}
    def helper(k):
        if k == 0:
            return 0
        if k in memo:
            return memo[k]
        res = float('inf')
        j = 1
        while j*j <= k:
            res = min(res, 1 + helper(k - j*j))
            j += 1
        memo[k] = res
        return res
    return helper(n)

# Example usage
if __name__ == '__main__':
    print(numSquares(12))  # Output: 3

Line Notes

memo = {}Initialize cache to store computed results

if k in memo:Return cached result if available to avoid recomputation

memo[k] = resStore computed minimal count for k

while j*j <= k:Try all perfect squares less than or equal to k

import java.util.HashMap;
public class Solution {
    private HashMap<Integer, Integer> memo = new HashMap<>();
    public int numSquares(int n) {
        return helper(n);
    }
    private int helper(int k) {
        if (k == 0) return 0;
        if (memo.containsKey(k)) return memo.get(k);
        int res = Integer.MAX_VALUE;
        for (int j = 1; j*j <= k; j++) {
            res = Math.min(res, 1 + helper(k - j*j));
        }
        memo.put(k, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numSquares(12)); // Output: 3
    }
}

Line Notes

private HashMap<Integer, Integer> memoCache to store results for subproblems

if (memo.containsKey(k))Return cached result if available

memo.put(k, res)Store computed result before returning

for (int j = 1; j*j <= k; j++)Try all perfect squares ≤ k

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

unordered_map<int,int> memo;

int helper(int k) {
    if (k == 0) return 0;
    if (memo.count(k)) return memo[k];
    int res = INT_MAX;
    for (int j = 1; j*j <= k; j++) {
        res = min(res, 1 + helper(k - j*j));
    }
    memo[k] = res;
    return res;
}

int numSquares(int n) {
    return helper(n);
}

int main() {
    cout << numSquares(12) << endl; // Output: 3
    return 0;
}

Line Notes

unordered_map<int,int> memo;Cache to store computed results

if (memo.count(k)) return memo[k];Return cached result if present

memo[k] = res;Store computed minimal count for k

for (int j = 1; j*j <= k; j++)Try all perfect squares ≤ k

function numSquares(n) {
    const memo = new Map();
    function helper(k) {
        if (k === 0) return 0;
        if (memo.has(k)) return memo.get(k);
        let res = Infinity;
        for (let j = 1; j*j <= k; j++) {
            res = Math.min(res, 1 + helper(k - j*j));
        }
        memo.set(k, res);
        return res;
    }
    return helper(n);
}

console.log(numSquares(12)); // Output: 3

Line Notes

const memo = new Map();Cache to store results for subproblems

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

memo.set(k, res);Store computed minimal count for k

for (let j = 1; j*j <= k; j++)Try all perfect squares ≤ k

⏱

Complexity

TimeO(n * sqrt(n)) due to memoized calls and iterating over squares

SpaceO(n) for memoization cache and recursion stack

Each subproblem solved once, each tries up to sqrt(n) squares

💡 For n=100, roughly 100*10=1000 operations, much faster than brute force.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for large inputs.

🧠

Bottom-Up Tabulation

💡 Tabulation builds the solution iteratively from the smallest subproblems up to n, avoiding recursion and making the process clearer and often faster.

Intuition

Create a dp array where dp[i] stores minimal squares for i, fill it from 0 to n using previously computed results.

Algorithm

1. Initialize dp array of size n+1 with large values, set dp[0] = 0.
2. For each i from 1 to n, try all perfect squares j*j ≤ i.
3. Update dp[i] = min(dp[i], 1 + dp[i - j*j]) to find minimal count.
4. Return dp[n] as the answer.

💡 This approach ensures all subproblems are solved once in increasing order, making it efficient and easy to debug.

Recurrence:dp[i] = min_{j*j ≤ i} (1 + dp[i - j*j])

</>

Code

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j*j <= i:
            dp[i] = min(dp[i], 1 + dp[i - j*j])
            j += 1
    return dp[n]

# Example usage
if __name__ == '__main__':
    print(numSquares(12))  # Output: 3

Line Notes

dp = [float('inf')] * (n + 1)Initialize dp array with infinity to represent uncomputed states

dp[0] = 0Base case: zero requires zero squares

for i in range(1, n + 1)Iterate over all targets from 1 to n

dp[i] = min(dp[i], 1 + dp[i - j*j])Update dp[i] by choosing square j*j and adding one to dp of remainder

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) dp[i] = Integer.MAX_VALUE;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numSquares(12)); // Output: 3
    }
}

Line Notes

int[] dp = new int[n + 1];Create dp array to store minimal counts

for (int i = 1; i <= n; i++) dp[i] = Integer.MAX_VALUE;Initialize dp with max values except dp[0]

for (int i = 1; i <= n; i++)Iterate over all targets

dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);Update dp[i] by considering square j*j

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

int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j*j <= i; j++) {
            dp[i] = min(dp[i], 1 + dp[i - j*j]);
        }
    }
    return dp[n];
}

int main() {
    cout << numSquares(12) << endl; // Output: 3
    return 0;
}

Line Notes

vector<int> dp(n + 1, INT_MAX);Initialize dp array with max values

dp[0] = 0;Base case for zero

for (int i = 1; i <= n; i++)Iterate over all sums from 1 to n

dp[i] = min(dp[i], 1 + dp[i - j*j]);Update dp[i] by choosing square j*j

function numSquares(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j*j <= i; j++) {
            dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);
        }
    }
    return dp[n];
}

console.log(numSquares(12)); // Output: 3

Line Notes

const dp = new Array(n + 1).fill(Infinity);Initialize dp array with Infinity

dp[0] = 0;Base case initialization

for (let i = 1; i <= n; i++)Iterate over all sums

dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);Update dp[i] by considering all squares

⏱

Complexity

TimeO(n * sqrt(n))

SpaceO(n)

For each i, we try all squares j*j ≤ i, which is up to sqrt(n)

💡 For n=10000, roughly 10000*100=1,000,000 operations, feasible with efficient implementation.

Interview Verdict: Accepted

This is the standard efficient solution for this problem.

🧠

Bottom-Up Tabulation (Space Optimized)

💡 Since dp only depends on previous states, we can optimize space by using a 1D array and iterating forward, which is already done here. This approach is the most efficient in both time and space.

Intuition

Use a single dp array to store minimal counts, updating it iteratively without recursion or extra cache.

Algorithm

1. Initialize dp array of size n+1 with infinity, dp[0] = 0.
2. For each number i from 1 to n, iterate over all perfect squares j*j ≤ i.
3. Update dp[i] with the minimal count by considering dp[i - j*j] + 1.
4. Return dp[n] as the minimal number of perfect squares.

💡 This approach uses only O(n) space and iterates in a way that ensures all needed subproblems are computed before use.

Recurrence:dp[i] = min(dp[i], 1 + dp[i - j*j])

</>

Code

def numSquares(n):
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        j = 1
        while j*j <= i:
            dp[i] = min(dp[i], 1 + dp[i - j*j])
            j += 1
    return dp[n]

# Example usage
if __name__ == '__main__':
    print(numSquares(12))  # Output: 3

Line Notes

dp = [float('inf')] * (n + 1)Initialize dp with infinity to represent uncomputed states

dp[0] = 0Base case: zero requires zero squares

for i in range(1, n + 1)Iterate over all targets from 1 to n

dp[i] = min(dp[i], 1 + dp[i - j*j])Update dp[i] by choosing square j*j and adding one to dp of remainder

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) dp[i] = Integer.MAX_VALUE;
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j*j <= i; j++) {
                dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.numSquares(12)); // Output: 3
    }
}

Line Notes

int[] dp = new int[n + 1];Create dp array to store minimal counts

for (int i = 1; i <= n; i++) dp[i] = Integer.MAX_VALUE;Initialize dp with max values except dp[0]

for (int i = 1; i <= n; i++)Iterate over all targets

dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);Update dp[i] by considering square j*j

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

int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j*j <= i; j++) {
            dp[i] = min(dp[i], 1 + dp[i - j*j]);
        }
    }
    return dp[n];
}

int main() {
    cout << numSquares(12) << endl; // Output: 3
    return 0;
}

Line Notes

vector<int> dp(n + 1, INT_MAX);Initialize dp array with max values

dp[0] = 0;Base case for zero

for (int i = 1; i <= n; i++)Iterate over all sums from 1 to n

dp[i] = min(dp[i], 1 + dp[i - j*j]);Update dp[i] by choosing square j*j

function numSquares(n) {
    const dp = new Array(n + 1).fill(Infinity);
    dp[0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j*j <= i; j++) {
            dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);
        }
    }
    return dp[n];
}

console.log(numSquares(12)); // Output: 3

Line Notes

const dp = new Array(n + 1).fill(Infinity);Initialize dp array with Infinity

dp[0] = 0;Base case initialization

for (let i = 1; i <= n; i++)Iterate over all sums

dp[i] = Math.min(dp[i], 1 + dp[i - j*j]);Update dp[i] by considering all squares

⏱

Complexity

TimeO(n * sqrt(n))

SpaceO(n)

Same as tabulation, but no recursion or extra cache needed

💡 This is the most practical approach for large inputs.

Interview Verdict: Accepted

This is the recommended approach to implement in interviews for efficiency and clarity.

📊

All Approaches - One-Glance Tradeoffs

💡 Tabulation or memoization are best for interviews; brute force is only for explanation.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down Memoization	O(n * sqrt(n))	O(n) memo + recursion stack	Possible but less likely	Yes with extra tracking	Good to code if comfortable with recursion
3. Bottom-Up Tabulation	O(n * sqrt(n))	O(n)	No	Yes with parent array	Preferred approach to code
4. Space Optimized Tabulation	O(n * sqrt(n))	O(n)	No	Yes with extra bookkeeping	Best for large inputs and final optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Explain the brute force recursive approach to show understanding of the problem structure.Step 3: Introduce memoization to optimize recursion and avoid repeated work.Step 4: Present bottom-up tabulation as an iterative alternative.Step 5: Discuss space optimization and final efficient solution.Step 6: Code the chosen approach and test with examples.

Time Allocation

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

What the Interviewer Tests

Interviewer tests your understanding of DP concepts, ability to optimize naive solutions, and coding accuracy.

Common Follow-ups

• Can you optimize space usage? → Use 1D dp array.
• What if you want to return the actual squares used? → Maintain a parent array to reconstruct solution.

💡 Follow-ups test your ability to optimize and extend solutions beyond just the minimal count.

🔍

Pattern Recognition

When to Use

1) Problem asks for minimal count or max value with unlimited use of items. 2) Items are perfect squares or similar. 3) Overlapping subproblems exist. 4) Need to minimize or maximize sum with repetition allowed.

Signature Phrases

'least number of perfect squares''sum to n using squares'

NOT This Pattern When

Problems with limited item usage or no overlapping subproblems (e.g., simple greedy) are different.

Similar Problems

Coin Change (Minimum Coins) - same unbounded knapsack structureInteger Break - partition integer into sum of integersWord Break - DP with substring partitions

Practice

1. The following code attempts to solve the coin change minimum coins problem. Identify the line containing the subtle bug that causes incorrect results or infinite recursion for amount=0.

def coinChange(coins, amount):
    def dfs(rem):
        if rem == 0:
            return 0
        res = float('inf')
        for coin in coins:
            if rem - coin >= 0:
                res = min(res, 1 + dfs(rem - coin))
        return res
    ans = dfs(amount)
    return ans if ans != float('inf') else -1

medium

A. Line 3: Missing base case for rem < 0

B. Line 6: Missing check for rem == 0 before recursion

C. Line 9: Returning res without checking if res is still infinity

D. Line 7: Incorrect condition rem - coin >= 0 instead of rem >= coin

Solution

1. Step 1: Analyze base cases in recursion

   Code handles rem == 0 but lacks base case for rem < 0, but since rem - coin >= 0 check prevents negative rem, no infinite recursion occurs.

2. Step 2: Check return value correctness

   Returning res directly without checking if res is still infinity can cause incorrect results when no valid coin combination exists.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Must check if res is infinity before returning to handle no solution cases correctly [OK]

Hint: Check if result is infinity before returning in recursion [OK]

Common Mistakes:

• Forgetting to handle no solution case
• Assuming rem == 0 base case suffices

2. What is the time complexity of the optimal bottom-up dynamic programming solution for the problem, given strs has length l, and the constraints are m zeros and n ones?

medium

A. O(l * (m + n))

B. O(l * m * n)

C. O(l * m * n * max_length_of_string)

D. O(2^l)

Solution

1. Step 1: Identify loops in the code

   Outer loop iterates over all strings (l), inner loops iterate over m and n capacities.

2. Step 2: Calculate total operations

   Each string causes updates over a 2D dp array of size (m+1)*(n+1), so total complexity is O(l * m * n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Nested loops over l, m, n -> O(l * m * n) [OK]

Hint: Nested loops over strings and both capacities multiply complexities [OK]

Common Mistakes:

• Confusing sum with product of m and n
• Including string length in complexity unnecessarily

3. Examine the following code snippet which attempts to solve the problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: zeros = s.count('0')

B. Line 10: for j in range(0, n - ones + 1):

C. Line 9: for i in range(0, m - zeros + 1): # iterating forwards

D. Line 11: dp[i + zeros][j + ones] = max(dp[i + zeros][j + ones], 1 + dp[i][j])

Solution

1. Step 1: Understand dp iteration direction

   To avoid counting the same string multiple times, dp must be updated backwards (from high to low indices).

2. Step 2: Identify bug in iteration

   Iterating forwards over i and j causes dp states to be reused within the same iteration, leading to overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Backward iteration is required for 0/1 knapsack variants [OK]

Hint: Forward iteration in 0/1 knapsack dp causes double counting [OK]

Common Mistakes:

• Forgetting to iterate dp backwards
• Miscounting zeros and ones

4. What is the time complexity of the DP with bitmask tabulation approach for partitioning an array of size n into k equal sum subsets, where the algorithm iterates over all subsets and elements?

medium

A. O(k^n) because it tries all assignments of elements to k buckets

B. O(n * 2^n) because it iterates over all subsets and elements

C. O(n * target) where target is the subset sum

D. O(2^n * n^2) due to nested loops over subsets and elements

Solution

1. Step 1: Identify loops in the algorithm

   The outer loop iterates over all subsets (2^n), inner loop over n elements.

2. Step 2: Calculate total complexity

   Combining loops gives O(n * 2^n). The target sum does not affect iteration count directly.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP bitmask iterates all subsets and elements [OK]

Hint: Bitmask DP complexity is n times 2^n subsets [OK]

Common Mistakes:

• Confusing brute force backtracking complexity with DP complexity
• Assuming complexity depends on target sum

5. The following code attempts to solve the Partition to K Equal Sum Subsets problem using DP with bitmask tabulation. Identify the line containing the subtle bug that can cause incorrect results or infinite loops.

def canPartitionKSubsets(nums, k):
    total = sum(nums)
    if total % k != 0:
        return False
    target = total // k
    n = len(nums)
    nums.sort()
    if nums[-1] > target:
        return False

    dp = [-1] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        if dp[mask] == -1:
            continue
        for i in range(n):
            if (mask & (1 << i)) == 0 and dp[mask] + nums[i] <= target:
                next_mask = mask | (1 << i)
                dp[next_mask] = (dp[mask] + nums[i]) % target

    return dp[(1 << n) - 1] == 0

medium

A. Line: dp = [-1] * (1 << n)

B. Line: if dp[next_mask] == -1: (missing in this code)

C. Line: nums.sort()

D. Line: dp[next_mask] = (dp[mask] + nums[i]) % target

Solution

1. Step 1: Identify missing condition

   The code lacks a check if dp[next_mask] is already set, so it overwrites states, causing incorrect results.

2. Step 2: Pinpoint the buggy line

   The line assigning dp[next_mask] unconditionally overwrites previous valid states, breaking memoization.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding "if dp[next_mask] == -1:" before assignment fixes bug [OK]

Hint: Always check if dp state is unset before assignment [OK]

Common Mistakes:

• Overwriting dp states without checking leads to incorrect answers
• Not pruning symmetric states increases runtime