Coding Patterns
Knapsack
Problems

Problems

Master the knapsack pattern by solving these carefully selected problems. Each problem demonstrates a different variation of the algorithm and builds your problem-solving skills progressively.

Easy Problems

1. Partition Equal Subset Sum

LeetCode 416 | Difficulty: Medium | Acceptance: 44.2%

  • Brief: Given an integer array, determine if the array can be partitioned into two subsets with equal sum.

  • Why this pattern?: Finding a subset that sums to half the total sum is exactly a knapsack problem where target value equals half of total sum.

  • Key Insight: If total sum is odd, return false immediately. Otherwise, we need to find a subset summing to total/2 using 0/1 knapsack.

  graph LR
    subgraph Example["Example: [1,5,11,5]"]
        A["Total Sum: 22"]
        B["Target: 11"]
        C["Subset [11]: Sum = 11"]
        D["Subset [1,5,5]: Sum = 11"]
    end

    A -->|Divide by 2| B
    B --> C
    B --> D

    style C fill:#aaf,stroke:#333
    style D fill:#aaf,stroke:#333

JavaScript:

/**
 * @param {number[]} nums
 * @return {boolean}
 */
function canPartition(nums) {
    const total = nums.reduce((sum, n) => sum + n, 0);
    if (total % 2 !== 0) return false;

    const target = total / 2;
    const dp = new Set([0]);

    for (const num of nums) {
        const newSums = [];
        for (const sum of dp) {
            const newSum = sum + num;
            if (newSum === target) return true;
            if (newSum < target) {
                newSums.push(newSum);
            }
        }
        newSums.forEach(s => dp.add(s));
    }

    return false;
}

Python:

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2 != 0:
        return False

    target = total // 2
    dp = set([0])

    for num in nums:
        new_sums = []
        for s in dp:
            new_sum = s + num
            if new_sum == target:
                return True
            if new_sum < target:
                new_sums.append(new_sum)
        dp.update(new_sums)

    return False

Java:

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;
        Set<Integer> dp = new HashSet<>();
        dp.add(0);

        for (int num : nums) {
            Set<Integer> newSums = new HashSet<>();
            for (int sum : dp) {
                int newSum = sum + num;
                if (newSum == target) return true;
                if (newSum < target) {
                    newSums.add(newSum);
                }
            }
            dp.addAll(newSums);
        }

        return false;
    }
}

C++:

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int total = accumulate(nums.begin(), nums.end(), 0);

        if (total % 2 != 0) return false;

        int target = total / 2;
        unordered_set<int> dp;
        dp.insert(0);

        for (int num : nums) {
            unordered_set<int> newSums;
            for (int sum : dp) {
                int newSum = sum + num;
                if (newSum == target) return true;
                if (newSum < target) {
                    newSums.insert(newSum);
                }
            }
            dp.insert(newSums.begin(), newSums.end());
        }

        return false;
    }
};

Go:

func canPartition(nums []int) bool {
    total := 0
    for _, n := range nums {
        total += n
    }

    if total%2 != 0 {
        return false
    }

    target := total / 2
    dp := make(map[int]bool)
    dp[0] = true

    for _, num := range nums {
        newSums := make(map[int]bool)
        for sum := range dp {
            newSum := sum + num
            if newSum == target {
                return true
            }
            if newSum < target {
                newSums[newSum] = true
            }
        }
        for k := range newSums {
            dp[k] = true
        }
    }

    return false
}

Ruby:

# @param {Integer[]} nums
# @return {Boolean}
def can_partition(nums)
  total = nums.sum
  return false if total.odd?

  target = total / 2
  dp = Set.new([0])

  nums.each do |num|
    new_sums = []
    dp.each do |sum|
      new_sum = sum + num
      return true if new_sum == target
      new_sums << new_sum if new_sum < target
    end
    dp.merge(new_sums)
  end

  false
end

Time Complexity:

O(N * target)
| Space Complexity:
O(target)

2. Coin Change

LeetCode 322 | Difficulty: Medium | Acceptance: 37.8%

  • Brief: Given coins of different denominations and a total amount, return the fewest number of coins needed to make up that amount.

  • Why this pattern?: Classic unbounded knapsack where we minimize coins to reach a target sum. Each coin can be used unlimited times.

  • Key Insight: Initialize dp array with infinity, dp[0] = 0. For each amount, try every coin that fits and track minimum.

  graph TD
    subgraph DP["DP Array for amount 11, coins [1,2,5]"]
        D0["dp[0] = 0"]
        D1["dp[1] = 1"]
        D2["dp[2] = 1"]
        D3["dp[3] = 2"]
        D4["dp[4] = 2"]
        D5["dp[5] = 1"]
        D11["dp[11] = 3"]
    end

    subgraph Solution["Solution"]
        S1["5"]
        S2["5"]
        S3["1"]
    end

    D11 --> Solution

    style D0 fill:#aaf,stroke:#333
    style D11 fill:#f9d,stroke:#333

JavaScript:

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
function coinChange(coins, amount) {
    const dp = new Array(amount + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= amount; i++) {
        for (const coin of coins) {
            if (coin <= i) {
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return dp[amount] === Infinity ? -1 : dp[amount];
}

Python:

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i:
                dp[i] = min(dp[i], dp[i - coin] + 1)

    return -1 if dp[amount] == float('inf') else dp[amount]

Java:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
}

C++:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;

        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }

        return dp[amount] > amount ? -1 : dp[amount];
    }
};

Go:

import "math"

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := range dp {
        dp[i] = amount + 1
    }
    dp[0] = 0

    for i := 1; i <= amount; i++ {
        for _, coin := range coins {
            if coin <= i {
                dp[i] = min(dp[i], dp[i-coin]+1)
            }
        }
    }

    if dp[amount] > amount {
        return -1
    }
    return dp[amount]
}

Ruby:

# @param {Integer[]} coins
# @param {Integer} amount
# @return {Integer}
def coin_change(coins, amount)
  dp = Array.new(amount + 1, Float::INFINITY)
  dp[0] = 0

  (1..amount).each do |i|
    coins.each do |coin|
      if coin <= i
        dp[i] = [dp[i], dp[i - coin] + 1].min
      end
    end
  end

  dp[amount] == Float::INFINITY ? -1 : dp[amount]
end

Time Complexity:

O(N * amount)
| Space Complexity:
O(amount)

Medium Problems

3. Coin Change II

LeetCode 518 | Difficulty: Medium | Acceptance: 53.2%

  • Brief: Given coins of different denominations and a total amount, return the number of combinations that make up that amount.

  • Why this pattern?: Unbounded knapsack counting combinations. Order doesn’t matter (1+2 is same as 2+1), so process coins outer loop.

  • Key Insight: For each coin, update dp from coin to amount. Initialize dp[0] = 1 (one way to make 0).

  graph TD
    subgraph Example["Example: amount=5, coins=[1,2,5]"]
        Comb1["1 way using only coin 1"]
        Comb2["Ways using coins 1,2"]
        CombAll["All combinations: 4 ways"]
    end

    subgraph Ways["Combinations"]
        W1["1+1+1+1+1"]
        W2["1+1+1+2"]
        W3["1+2+2"]
        W4["5"]
    end

    Comb1 --> Comb2 --> CombAll
    CombAll --> Ways

    style CombAll fill:#f9d,stroke:#333

JavaScript:

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
function change(amount, coins) {
    const dp = new Array(amount + 1).fill(0);
    dp[0] = 1;

    for (const coin of coins) {
        for (let i = coin; i <= amount; i++) {
            dp[i] += dp[i - coin];
        }
    }

    return dp[amount];
}

Python:

def change(amount: int, coins: list[int]) -> int:
    dp = [0] * (amount + 1)
    dp[0] = 1

    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] += dp[i - coin]

    return dp[amount]

Java:

class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
}

C++:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;

        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }

        return dp[amount];
    }
};

Go:

func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1

    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] += dp[i-coin]
        }
    }

    return dp[amount]
}

Ruby:

# @param {Integer} amount
# @param {Integer[]} coins
# @return {Integer}
def change(amount, coins)
  dp = Array.new(amount + 1, 0)
  dp[0] = 1

  coins.each do |coin|
    (coin..amount).each do |i|
      dp[i] += dp[i - coin]
    end
  end

  dp[amount]
end

Time Complexity:

O(N * amount)
| Space Complexity:
O(amount)

4. Target Sum

LeetCode 494 | Difficulty: Medium | Acceptance: 39.1%

  • Brief: Given an array of integers and a target, build an expression by adding + or - before each integer. Find number of different expressions equal to target.

  • Why this pattern?: Can be reduced to subset sum problem. P - N = target where P is sum of positive numbers, N is sum of negative numbers. This becomes finding subset that sums to (total + target) / 2.

  • Key Insight: If total + target is odd or target > total, no solution. Otherwise, count ways to pick subset summing to (total + target) / 2.

  graph TD
    subgraph Example["Example: nums=[1,1,1,1,1], target=3"]
        Total["Total sum: 5"]
        TargetPos["target: 3"]
        Calc["(5 + 3) / 2 = 4"]
        Meaning["Need subset summing to 4"]
        Result["5 ways: choose any 4 ones"]
    end

    Total --> Calc
    TargetPos --> Calc
    Calc --> Meaning
    Meaning --> Result

    style Result fill:#f9d,stroke:#333

JavaScript:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
function findTargetSumWays(nums, target) {
    const total = nums.reduce((sum, n) => sum + n, 0);

    if (Math.abs(target) > total || (total + target) % 2 !== 0) {
        return 0;
    }

    const subsetSum = (total + target) / 2;
    const dp = new Array(subsetSum + 1).fill(0);
    dp[0] = 1;

    for (const num of nums) {
        for (let i = subsetSum; i >= num; i--) {
            dp[i] += dp[i - num];
        }
    }

    return dp[subsetSum];
}

Python:

def find_target_sum_ways(nums: list[int], target: int) -> int:
    total = sum(nums)

    if abs(target) > total or (total + target) % 2 != 0:
        return 0

    subset_sum = (total + target) // 2
    dp = [0] * (subset_sum + 1)
    dp[0] = 1

    for num in nums:
        for i in range(subset_sum, num - 1, -1):
            dp[i] += dp[i - num]

    return dp[subset_sum]

Java:

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int total = 0;
        for (int num : nums) total += num;

        if (Math.abs(target) > total || (total + target) % 2 != 0) {
            return 0;
        }

        int subsetSum = (total + target) / 2;
        int[] dp = new int[subsetSum + 1];
        dp[0] = 1;

        for (int num : nums) {
            for (int i = subsetSum; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }

        return dp[subsetSum];
    }
}

C++:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int total = accumulate(nums.begin(), nums.end(), 0);

        if (abs(target) > total || (total + target) % 2 != 0) {
            return 0;
        }

        int subsetSum = (total + target) / 2;
        vector<int> dp(subsetSum + 1, 0);
        dp[0] = 1;

        for (int num : nums) {
            for (int i = subsetSum; i >= num; i--) {
                dp[i] += dp[i - num];
            }
        }

        return dp[subsetSum];
    }
};

Go:

import "math"

func findTargetSumWays(nums []int, target int) int {
    total := 0
    for _, n := range nums {
        total += n
    }

    if math.Abs(float64(target)) > float64(total) || (total+target)%2 != 0 {
        return 0
    }

    subsetSum := (total + target) / 2
    dp := make([]int, subsetSum+1)
    dp[0] = 1

    for _, num := range nums {
        for i := subsetSum; i >= num; i-- {
            dp[i] += dp[i-num]
        }
    }

    return dp[subsetSum]
}

Ruby:

# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer}
def find_target_sum_ways(nums, target)
  total = nums.sum

  return 0 if target.abs > total || (total + target).odd?

  subset_sum = (total + target) / 2
  dp = Array.new(subset_sum + 1, 0)
  dp[0] = 1

  nums.each do |num|
    (subset_sum).downto(num).each do |i|
      dp[i] += dp[i - num]
    end
  end

  dp[subset_sum]
end

Time Complexity:

O(N * subsetSum)
| Space Complexity:
O(subsetSum)

5. Ones and Zeroes

LeetCode 474 | Difficulty: Medium | Acceptance: 47.1%

  • Brief: Given a binary string array and integers m and n, return the size of the largest subset of strs with at most m zeros and n ones.

  • Why this pattern?: Multi-dimensional knapsack with two constraints (zero budget and one budget). Each string is an item with two “weights”.

  • Key Insight: Use 2D DP where dp[i][j] = max subset size using at most i zeros and j ones. Process strings one by one, updating backwards.

  graph TD
    subgraph Example["Example: strs=['10','0001','111001'], m=5, n=3"]
        S1["10: 1 zero, 1 one"]
        S2["0001: 3 zeros, 1 one"]
        S3["111001: 2 zeros, 4 ones"]
        Result["Max subset size: 4"]
    end

    subgraph Selection["Selection: 10, 0001"]
        Zeros["Total zeros: 4"]
        Ones["Total ones: 2"]
        Check["4 <= 5, 2 <= 3: Valid"]
    end

    S1 --> Selection
    S2 --> Selection
    S3 -.skipped.-> Result
    Selection --> Result

    style Result fill:#f9d,stroke:#333

JavaScript:

/**
 * @param {string[]} strs
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
function findMaxForm(strs, m, n) {
    const dp = Array(m + 1).fill().map(() => Array(n + 1).fill(0));

    for (const str of strs) {
        let zeros = 0, ones = 0;
        for (const char of str) {
            if (char === '0') zeros++;
            else ones++;
        }

        for (let i = m; i >= zeros; i--) {
            for (let j = n; j >= ones; j--) {
                dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
            }
        }
    }

    return dp[m][n];
}

Python:

def find_max_form(strs: list[str], m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for s in strs:
        zeros = s.count('0')
        ones = len(s) - zeros

        for i in range(m, zeros - 1, -1):
            for j in range(n, ones - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1)

    return dp[m][n]

Java:

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] dp = new int[m + 1][n + 1];

        for (String s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s.toCharArray()) {
                if (c == '0') zeros++;
                else ones++;
            }

            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = Math.max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
}

C++:

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        for (const string& s : strs) {
            int zeros = 0, ones = 0;
            for (char c : s) {
                if (c == '0') zeros++;
                else ones++;
            }

            for (int i = m; i >= zeros; i--) {
                for (int j = n; j >= ones; j--) {
                    dp[i][j] = max(dp[i][j], dp[i - zeros][j - ones] + 1);
                }
            }
        }

        return dp[m][n];
    }
};

Go:

import "strings"

func findMaxForm(strs []string, m, n int) int {
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }

    for _, s := range strs {
        zeros := strings.Count(s, "0")
        ones := len(s) - zeros

        for i := m; i >= zeros; i-- {
            for j := n; j >= ones; j-- {
                dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
            }
        }
    }

    return dp[m][n]
}

Ruby:

# @param {String[]} strs
# @param {Integer} m
# @param {Integer} n
# @return {Integer}
def find_max_form(strs, m, n)
  dp = Array.new(m + 1) { Array.new(n + 1, 0) }

  strs.each do |s|
    zeros = s.count('0')
    ones = s.length - zeros

    (m).downto(zeros).each do |i|
      (n).downto(ones).each do |j|
        dp[i][j] = [dp[i][j], dp[i - zeros][j - ones] + 1].max
      end
    end
  end

  dp[m][n]
end

Time Complexity:

O(L * m * n)
where L is total length of all strings | Space Complexity:
O(m * n)

Hard Problems

6. Partition to K Equal Sum Subsets

LeetCode 698 | Difficulty: Medium | Acceptance: 44.5%

  • Brief: Given an integer array nums and positive integer k, determine if it’s possible to divide array into k non-empty subsets with equal sum.

  • Why this pattern?: Can be seen as subset selection with k-1 constraints. Not pure knapsack but related subset selection principle.

  • Key Insight: If total sum not divisible by k, return false. Sort descending for better pruning. Backtrack to find k-1 subsets.

  graph TD
    subgraph Example["Example: nums=[4,3,2,3,5,2,1], k=4"]
        Total["Total sum: 20"]
        Target["Target per subset: 5"]
        Subset1["[5] = 5"]
        Subset2["[4,1] = 5"]
        Subset3["[3,2] = 5"]
        Subset4["[3,2] = 5"]
        Success["Possible: Yes"]
    end

    Total -->|Divide by k| Target
    Target --> Success
    Subset1 --> Success
    Subset2 --> Success
    Subset3 --> Success
    Subset4 --> Success

    style Success fill:#aaf,stroke:#333

JavaScript:

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {boolean}
 */
function canPartitionKSubsets(nums, k) {
    const total = nums.reduce((sum, n) => sum + n, 0);
    if (total % k !== 0) return false;

    const target = total / k;
    nums.sort((a, b) => b - a);

    if (nums[0] > target) return false;

    const used = new Array(nums.length).fill(false);

    const backtrack = (start, currentSum, subsetsFormed) => {
        if (subsetsFormed === k - 1) return true;
        if (currentSum === target) {
            return backtrack(0, 0, subsetsFormed + 1);
        }

        for (let i = start; i < nums.length; i++) {
            if (used[i] || currentSum + nums[i] > target) continue;

            used[i] = true;
            if (backtrack(i + 1, currentSum + nums[i], subsetsFormed)) {
                return true;
            }
            used[i] = false;

            if (currentSum === 0) break;
        }

        return false;
    };

    return backtrack(0, 0, 0);
}

Python:

def can_partition_k_subsets(nums: list[int], k: int) -> bool:
    total = sum(nums)
    if total % k != 0:
        return False

    target = total // k
    nums.sort(reverse=True)

    if nums[0] > target:
        return False

    used = [False] * len(nums)

    def backtrack(start, current_sum, subsets_formed):
        if subsets_formed == k - 1:
            return True
        if current_sum == target:
            return backtrack(0, 0, subsets_formed + 1)

        for i in range(start, len(nums)):
            if used[i] or current_sum + nums[i] > target:
                continue

            used[i] = True
            if backtrack(i + 1, current_sum + nums[i], subsets_formed):
                return True
            used[i] = False

            if current_sum == 0:
                break

        return False

    return backtrack(0, 0, 0)

Java:

class Solution {
    private int[] nums;
    private int target;
    private boolean[] used;

    public boolean canPartitionKSubsets(int[] nums, int k) {
        int total = 0;
        for (int num : nums) total += num;

        if (total % k != 0) return false;

        target = total / k;
        Arrays.sort(nums);
        reverse(nums);

        if (nums[0] > target) return false;

        this.nums = nums;
        used = new boolean[nums.length];

        return backtrack(0, 0, 0);
    }

    private boolean backtrack(int start, int currentSum, int subsetsFormed) {
        if (subsetsFormed == k - 1) return true;
        if (currentSum == target) {
            return backtrack(0, 0, subsetsFormed + 1);
        }

        for (int i = start; i < nums.length; i++) {
            if (used[i] || currentSum + nums[i] > target) continue;

            used[i] = true;
            if (backtrack(i + 1, currentSum + nums[i], subsetsFormed)) {
                return true;
            }
            used[i] = false;

            if (currentSum == 0) break;
        }

        return false;
    }

    private void reverse(int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i < j) {
            int temp = arr[i];
            arr[i++] = arr[j];
            arr[j--] = temp;
        }
    }
}

C++:

class Solution {
    vector<int> nums;
    int target;
    vector<bool> used;

    bool backtrack(int start, int currentSum, int subsetsFormed) {
        if (subsetsFormed == k - 1) return true;
        if (currentSum == target) {
            return backtrack(0, 0, subsetsFormed + 1);
        }

        for (int i = start; i < nums.size(); i++) {
            if (used[i] || currentSum + nums[i] > target) continue;

            used[i] = true;
            if (backtrack(i + 1, currentSum + nums[i], subsetsFormed)) {
                return true;
            }
            used[i] = false;

            if (currentSum == 0) break;
        }

        return false;
    }

public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        int total = accumulate(nums.begin(), nums.end(), 0);

        if (total % k != 0) return false;

        target = total / k;
        sort(nums.rbegin(), nums.rend());

        if (nums[0] > target) return false;

        this->nums = nums;
        used.assign(nums.size(), false);

        return backtrack(0, 0, 0);
    }
};

Go:

func canPartitionKSubsets(nums []int, k int) bool {
    total := 0
    for _, n := range nums {
        total += n
    }

    if total%k != 0 {
        return false
    }

    target := total / k
    sort.Sort(sort.Reverse(sort.IntSlice(nums)))

    if nums[0] > target {
        return false
    }

    used := make([]bool, len(nums))

    var backtrack func(start, currentSum, subsetsFormed int) bool
    backtrack = func(start, currentSum, subsetsFormed int) bool {
        if subsetsFormed == k-1 {
            return true
        }
        if currentSum == target {
            return backtrack(0, 0, subsetsFormed+1)
        }

        for i := start; i < len(nums); i++ {
            if used[i] || currentSum+nums[i] > target {
                continue
            }

            used[i] = true
            if backtrack(i+1, currentSum+nums[i], subsetsFormed) {
                return true
            }
            used[i] = false

            if currentSum == 0 {
                break
            }
        }

        return false
    }

    return backtrack(0, 0, 0)
}

Ruby:

# @param {Integer[]} nums
# @param {Integer} k
# @return {Boolean}
def can_partition_k_subsets(nums, k)
  total = nums.sum
  return false if total % k != 0

  target = total / k
  nums.sort! { |a, b| b <=> a }
  return false if nums.first > target

  used = Array.new(nums.length, false)

  backtrack = lambda do |start, current_sum, subsets_formed|
    return true if subsets_formed == k - 1
    return backtrack.call(0, 0, subsets_formed + 1) if current_sum == target

    (start...nums.length).each do |i|
      next if used[i] || current_sum + nums[i] > target

      used[i] = true
      if backtrack.call(i + 1, current_sum + nums[i], subsets_formed)
        return true
      end
      used[i] = false

      break if current_sum == 0
    end

    false
  end

  backtrack.call(0, 0, 0)
end

Time Complexity:

O(k * 2^N)
| Space Complexity:
O(N)

Recommended Study Order

Start with Partition Equal Subset Sum to understand how subset selection maps to knapsack. Then practice Coin Change to master the unbounded knapsack with minimization. Target Sum teaches you to identify knapsack in disguised problems. Ones and Zeroes extends to multi-dimensional constraints. Finally, Partition to K Equal Sum Subsets combines backtracking with subset selection.

Common Mistakes

  • Wrong iteration order: Forward vs backward iteration determines if items can be reused
  • Overflow: Large sums can exceed integer limits, use long types
  • Missing base cases: Always initialize dp[0] appropriately
  • Wrong constraint handling: In multi-dimensional problems, update all constraints simultaneously

Ready to see templates? Check out our Code Templates for memorizable implementations.

Pro Tip: The key difference between 0/1 and unbounded knapsack is iteration direction. For 0/1, iterate backwards to prevent reuse. For unbounded, iterate forwards to allow unlimited reuse.