Practice
Solution
Step 1: Understand problem constraints
The problem requires counting combinations (order does not matter) of unlimited coins summing to amount.Step 2: Identify suitable algorithm
Greedy fails as it misses combinations; backtracking without memoization is exponential; permutations count order, not combinations. DP with 1D array iterating coins first ensures combinations are counted correctly.Final Answer:
Option B -> Option BQuick Check:
DP approach counts combinations efficiently [OK]
- Using greedy approach
- Counting permutations instead of combinations
- Not using DP or memoization
findTargetSumWays([1, 2], 1)?Solution
Step 1: Trace initial dp array
total=3, offset=3, dp=[0,0,0,1,0,0,0] (index 3 corresponds to sum 0)Step 2: Process num=1 and num=2 updating dp
After num=1, dp counts ways to reach sums -1 and 1. After num=2, dp counts ways to reach sums -3,-1,1,3. dp[target+offset]=dp[1+3]=dp[4]=2.Final Answer:
Option D -> Option DQuick Check:
Two ways: +1-2 and -1+2 sum to 1 [OK]
- Off-by-one errors in indexing dp array
def knapsack_space_optimized(weights, values, W):
n = len(weights)
dp = [0] * (W + 1)
for i in range(n):
for w in range(weights[i], W + 1): # Note: iterating forwards
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[W]Solution
Step 1: Analyze iteration order in inner loop
The inner loop iterates forwards from weights[i] to W, which causes the current item to be counted multiple times in the same iteration, violating 0/1 knapsack constraints.Step 2: Correct iteration direction
Iterating backwards (from W down to weights[i]) ensures each item is only counted once per capacity, preserving correctness.Final Answer:
Option A -> Option AQuick Check:
Forward iteration causes overcounting items [OK]
- Iterating forwards in dp array updates for 0/1 knapsack.
Solution
Step 1: Identify sorting cost
Sorting n jobs by end time costs O(n log n).Step 2: Analyze DP loop with binary search
For each job, binary search among ends array costs O(log n), repeated n times -> O(n log n).Final Answer:
Option D -> Option DQuick Check:
Sorting + n binary searches dominate; no nested O(n^2) loops [OK]
- Assuming O(n^2) due to DP
- Ignoring binary search cost
- Confusing max end time W with input size n
Solution
Step 1: Understand 0/1 knapsack constraints
Each coin can be used once, so dp updates must avoid reuse within same iteration.Step 2: Identify correct iteration order
Iterating amounts backward ensures dp[w] uses dp[w - coin] from previous iteration, preventing reuse.Step 3: Evaluate other options
Forward iteration allows reuse; recursion without memoization is inefficient; greedy is incorrect.Final Answer:
Option A -> Option AQuick Check:
Backward iteration is standard for 0/1 knapsack to avoid reuse [OK]
- Using forward iteration causing reuse
- Relying on greedy or naive recursion
