101 Logo
onenoughtone

Solution Approach

Solution Overview

There are 3 main approaches to solve this problem:

  1. Recursive Backtracking Approach - Complex approach
  2. Dynamic Programming Approach - Complex approach
  3. Space-Optimized Dynamic Programming - Complex approach

Approach 1: Recursive Backtracking Approach

The recursive backtracking approach is a natural fit for the Subset Sum problem. For each gear item, we have two choices: include it in our backpack or exclude it. We recursively explore both options and check if any combination gives us the exact capacity we're looking for.

This approach follows the Selection Pattern of recursion, where we make binary decisions (include/exclude) for each element.

Algorithm:

  1. Define a recursive function subsetSum(gearWeights, capacity, index) that takes the array of gear weights, the remaining capacity, and the current index.
  2. Base cases:
  3. - If the remaining capacity is 0, return true (we've found a valid subset).
  4. - If the remaining capacity is negative or we've processed all items, return false.
  5. Recursive cases:
  6. - Exclude the current item: subsetSum(gearWeights, capacity, index + 1)
  7. - Include the current item: subsetSum(gearWeights, capacity - gearWeights[index], index + 1)
  8. Return true if either of the recursive calls returns true, otherwise return false.
  9. The main function should call the recursive function with the initial capacity and index 0.

Time Complexity:

O(2^n)

In the worst case, we explore all 2^n possible subsets of n items, resulting in exponential time complexity.

Space Complexity:

O(n)

The recursion stack can grow up to n levels deep, corresponding to the number of items.

Approach 2: Dynamic Programming Approach

The dynamic programming approach optimizes the recursive solution by storing the results of subproblems to avoid redundant calculations. We use a 2D table where dp[i][j] represents whether there's a subset of the first i items that sums to j.

This approach significantly improves the time complexity from exponential to polynomial, making it feasible for larger inputs.

Algorithm:

  1. Create a 2D boolean table dp of size (n+1) × (capacity+1), where n is the number of items.
  2. Initialize dp[0][0] = true (an empty subset sums to 0), and dp[0][j] = false for j > 0 (an empty subset can't sum to a positive value).
  3. For each item i from 1 to n:
  4. - For each possible capacity j from 0 to capacity:
  5. - If j < gearWeights[i-1], set dp[i][j] = dp[i-1][j] (can't include this item).
  6. - Otherwise, set dp[i][j] = dp[i-1][j] || dp[i-1][j - gearWeights[i-1]] (either exclude or include this item).
  7. Return dp[n][capacity], which indicates whether there's a subset of all n items that sums to the capacity.

Time Complexity:

O(n × capacity)

We fill a table of size (n+1) × (capacity+1), where n is the number of items and capacity is the backpack capacity.

Space Complexity:

O(n × capacity)

We use a 2D table of size (n+1) × (capacity+1) to store the results of subproblems.

Approach 3: Space-Optimized Dynamic Programming

We can optimize the space complexity of the dynamic programming approach by using a 1D array instead of a 2D table. This is possible because at each step, we only need the results from the previous row of the table.

This approach maintains the same time complexity while reducing the space complexity from O(n × capacity) to O(capacity).

Algorithm:

  1. Create a 1D boolean array dp of size (capacity+1).
  2. Initialize dp[0] = true (an empty subset sums to 0), and dp[j] = false for j > 0 (an empty subset can't sum to a positive value).
  3. For each item i from 0 to n-1:
  4. - Iterate from capacity down to gearWeights[i]:
  5. - Update dp[j] = dp[j] || dp[j - gearWeights[i]] (either exclude or include this item).
  6. Return dp[capacity], which indicates whether there's a subset that sums to the capacity.

Time Complexity:

O(n × capacity)

We still need to process each item and each possible capacity, resulting in the same time complexity as the 2D approach.

Space Complexity:

O(capacity)

We use a 1D array of size (capacity+1) to store the results, which is a significant improvement over the 2D approach.

Pseudocode

solution.pseudo
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function canPackExactly(gearWeights, capacity):
    return subsetSum(gearWeights, capacity, 0)
 
function subsetSum(gearWeights, capacity, index):
    // Base cases
    if capacity == 0:
        return true
    if capacity < 0 or index >= gearWeights.length:
        return false
 
    // Recursive cases
 
    // Exclude the current item
    if subsetSum(gearWeights, capacity, index + 1):
        return true
 
    // Include the current item
    return subsetSum(gearWeights, capacity - gearWeights[index], index + 1)
PreviousNext
ProblemSolutionCode
101 Logo
onenoughtone